例：hnitoj_1490
1 例：hnitoj_1490 2 3 4 #include <iostream> 5 #include <cstring> 6 using namespace std; 7 int dp[30][80005]; 8 int path[30][80005]; 9 int v[30]; 10 void solve(int k, int cap){ 11 while(k && cap){ 12 if(dp[k][cap] == dp[k - 1][cap - v[k]] + v[k]){ 13 cout << v[k] << ' '; 14 cap -= v[k]; 15 } 16 k--; 17 } 18 } 19 20 void solve1(int k,int cap){ 21 while(k&&cap){ 22 if(path[k][cap]>0){ 23 cout << v[k] <<' '; 24 cap -= v[k]; 25 } 26 k--; 27 } 28 } 29 30 int main() 31 { 32 int T, k, cap; 33 cin >> T; 34 memset(dp, 0, sizeof(dp)); 35 while(T--){ 36 int n, m; 37 cin >> n >> m; 38 v[0] = 0; 39 for(k = 1; k <= m; k++) 40 cin >> v[k]; 41 for(k = 1; k <= m; k++){ 42 for(cap = 1; cap <= n; cap++){ 43 if(cap < v[k] ) 44 dp[k][cap] = dp[k - 1][cap]; 45 else{ 46 dp[k][cap] = max(dp[k - 1][cap], dp[k - 1][cap - v[k]] + v[k]); 47 if(dp[k][cap] == dp[k - 1][cap - v[k]] + v[k]) 48 path[k][cap] = 1; 49 } 50 } 51 } 52 solve1(m, n); 53 cout << endl; 54 cout << dp[m][n] << endl; 55 } 56 return 0; 57 } 58 59 } 60 } 61 solve(m, n); 62 cout << endl; 63 cout << dp[m][n] << endl; 64 } 65 return 0; 66 }