第四个测试点死活过不去 求大佬帮忙看一下 感激不尽
//26分 第四个测试点无法通过 原因为超时 错误可能在dfs中
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
int dp[110][10005];
int M;//monety to pay
int N;//coins num
int coins[10005];
vector<int> temp;
vector<int> path;
int pathnum = 0;
vector<int> bestpath;
void print(){//与当前字典序最小的路径比较 并更新字典序最小的路径if(path.size() > pathnum){pathnum = path.size();bestpath = path;}else if(path.size() == pathnum){int i = path.size() - 1;while(path[i] == bestpath[i] && i >= 0){i --;}if(i != -1){if(path[i] < bestpath[i]){bestpath = path;}}}
}
int bag(int weight, int numberofcoin){//dp函数if(dp[weight][numberofcoin] != -1){return dp[weight][numberofcoin];}int a;if(weight >= coins[numberofcoin]){a = bag(weight - coins[numberofcoin], numberofcoin - 1) + coins[numberofcoin];}else{a = 0;}int b = bag(weight,numberofcoin - 1);if(a >= b){dp[weight][numberofcoin] = a;return a;}else{dp[weight][numberofcoin] = b;return b;}
}
void dfs(int M, int N){//对dp数组 dfs 搜寻所有路径if(N == 0){path = temp;print();}else{if(M >= coins[N]){if(dp[M][N] == dp[M - coins[N]][N - 1] + coins[N]){temp.push_back(coins[N]);dfs(M - coins[N], N - 1);temp.pop_back();}}if(dp[M][N] == dp[M][N - 1]){dfs(M, N-1);}}return;
}
int main(int argc, char *argv[]) {memset(dp, -1, sizeof(dp));scanf("%d %d", &N, &M);for(int i = 1; i <= N; i ++){int temp;scanf("%d", &temp);coins[i] = temp;}sort(coins + 1, coins + N + 1);for(int i = 0; i < 110; i ++){dp[i][0] = 0;}for(int i = 0; i < 1005; i ++){dp[0][i] = 0;}int num = bag(M,N);if(num != M){printf("No Solution");return 0;}dfs(M, N);for(int i = bestpath.size() - 1; i >= 0; i --){printf("%d", bestpath[i]);if(i > 0) printf(" ");}return 0;
}