01背包路径回溯

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define N 37
 4 int n;
 5 int p[40],a[40],c[40],m[40],g[40];
 6 int P,A,C,M;
 7 short dp[N][N][N][N];
 8 bool tk[N][N][N][N][N];
 9 int main()
10 {
11     scanf("%d",&n);
12     for (int i = 1; i <=n ; ++i) {
13         scanf("%d %d %d %d %d",&p[i],&a[i],&c[i],&m[i],&g[i]);
14     }
15     scanf("%d %d %d %d",&P,&A,&C,&M);
16     for (int i = 1; i <=n ; ++i) {
17         for (int j = P; j >=p[i] ; j--) {
18             for (int k = A; k >=a[i] ; k--) {
19                 for (int l = C; l >=c[i] ; l--) {
20                     for (int x = M; x >=m[i] ; x--) {
21                         if(dp[j][k][l][x]<=dp[j-p[i]][k-a[i]][l-c[i]][x-m[i]]+g[i])
22                         {
23                             dp[j][k][l][x] = dp[j-p[i]][k-a[i]][l-c[i]][x-m[i]]+g[i];
24                             tk[i][j][k][l][x]=true;
25                         }
26                     }
27                 }
28             }
29         }
30     }
31     vector<int>ans;
32     for(int i=n; i>0; --i) {
33         if(tk[i][P][A][C][M] == 1) {
34             ans.push_back(i-1);
35             P -= p[i], A -= a[i], C -= c[i], M -= m[i];
36         }
37         if(P<0 || A<0 || C<0 || M<0) break;
38     }
39     printf("%d\n",(int)ans.size());
40     sort(ans.begin(),ans.end());
41     for(auto i : ans) printf("%d\n", i);
42     return 0;
43 }