题目链接（貌似未报名的不能进去）：https://www.nowcoder.com/acm/contest/141/A
题目：
题意：背包题意，并打印路径。
思路：正常背包思路，不过五维的dp很容易爆内存，比赛时无限爆，后面队友提醒用short就过了。不过也可以用滚动减少内存消耗，两种代码实现都贴一下吧~
五维代码实现如下：
1 #include <set> 2 #include <map> 3 #include <queue> 4 #include <stack> 5 #include <cmath> 6 #include <bitset> 7 #include <cstdio> 8 #include <string> 9 #include <vector> 10 #include <cstdlib> 11 #include <cstring> 12 #include <iostream> 13 #include <algorithm> 14 using namespace std; 15 16 typedef long long ll; 17 typedef unsigned long long ull; 18 19 #define lson i<<1 20 #define rson i<<1|1 21 #define bug printf("********* "); 22 #define FIN freopen("D://code//in.txt", "r", stdin); 23 #define debug(x) cout<<"["<<x<<"]" <<endl; 24 #define IO ios::sync_with_stdio(false),cin.tie(0); 25 26 const double eps = 1e-8; 27 const int mod = 10007; 28 const int maxn = 1e7 + 7; 29 const double pi = acos(-1); 30 const int inf = 0x3f3f3f3f; 31 const ll INF = 0x3f3f3f3f3f3f3f3f; 32 33 short n, P, A, C, M; 34 short p[37], a[37], c[37], m[37], g[37], cnt[37]; 35 short dp[37][37][37][37][37]; 36 bool vis[37][37][37][37][37]; 37 38 int main() { 39 //FIN; 40 cin >>n; 41 for(int i = 1; i <= n; i++) { 42 cin >>p[i] >>a[i] >> c[i] >>m[i] >>g[i]; 43 } 44 cin >>P >>A >>C >>M; 45 int flag1 = 0, flag2 = 0, flag3 = 0, flag4 = 0, mx = 0; 46 for(int i = 1; i <= n; i++) { 47 for(int j = 0; j <= P; j++) { 48 for(int k = 0; k <= A; k++) { 49 for(int l = 0; l <= C; l++) { 50 for(int t = 0; t <= M; t++) { 51 dp[i][j][k][l][t] = dp[i-1][j][k][l][t]; 52 if(j >= p[i] && k >= a[i] && l >= c[i] && t >= m[i]) { 53 if(dp[i-1][j-p[i]][k-a[i]][l-c[i]][t-m[i]] + g[i] > dp[i-1][j][k][l][t]) { 54 dp[i][j][k][l][t] = dp[i-1][j-p[i]][k-a[i]][l-c[i]][t-m[i]] + g[i]; 55 vis[i][j][k][l][t] = true; 56 } 57 } 58 } 59 } 60 } 61 } 62 } 63 for(int j = 0; j <= P; j++) { 64 for(int k = 0; k <= A; k++) { 65 for(int l = 0; l <= C; l++) { 66 for(int t = 0; t <= M; t++) { 67 if(dp[n][j][k][l][t] > mx) { 68 flag1 = j, flag2 = k, flag3 = l, flag4 = t; 69 mx = dp[n][j][k][l][t]; 70 71 } 72 } 73 } 74 } 75 } 76 int num = 0; 77 for(int i = n; i >= 1; i--) { 78 if(vis[i][flag1][flag2][flag3][flag4]) { 79 cnt[num++] = i - 1; 80 flag1 -= p[i]; 81 flag2 -= a[i]; 82 flag3 -= c[i]; 83 flag4 -= m[i]; 84 } 85 } 86 cout <<num <<endl; 87 for(int i = num - 1; i >= 0; i--) { 88 cout <<cnt[i] <<" "; 89 } 90 cout <<" "; 91 return 0; 92 }
滚动数组实现如下：
1 #include <bits/stdc++.h> 2 #define fi first 3 #define se second 4 #define lson l,m,rt<<1 5 #define rson m+1,r,rt<<1|1 6 #define lowbit(x) x&-x 7 #define MP make_pair 8 #define pb push_back 9 #define debug(x) cout<<"x= "<<x<<endl; 10 #define FIN freopen("in.txt","r",stdin); 11 using namespace std; 12 typedef long long ll; 13 typedef vector<int> vi; 14 typedef pair<int,int>pii; 15 const int mod=1e9+7; 16 const ll infll=0x3f3f3f3f3f3f3f3f; 17 const int MX = 1e5 + 7; 18 const int INF = 0x3f3f3f3f; 19 20 short n; 21 short dp[37][37][37][37]; 22 bool vis[37][37][37][37][37]; 23 short p[37],a[37],c[37],m[37],g[37]; 24 short P,A,C,M; 25 26 int main(){ 27 //FIN; 28 cin>>n; 29 for(int i=1;i<=n;i++) 30 cin>>p[i]>>a[i]>>c[i]>>m[i]>>g[i]; 31 cin>>P>>A>>C>>M; 32 memset(dp,0,sizeof(dp)); 33 memset(vis,0,sizeof(vis)); 34 for(int i=1;i<=n;i++){ 35 for(int j=P;j>=p[i];j--){ 36 for(int k=A;k>=a[i];k--){ 37 for(int l=C;l>=c[i];l--){ 38 for(int o=M;o>=m[i];o--){ 39 if(dp[j][k][l][o] > dp[j-p[i]][k-a[i]][l-c[i]][o-m[i]]+g[i]) continue; 40 dp[j][k][l][o]=dp[j-p[i]][k-a[i]][l-c[i]][o-m[i]]+g[i]; 41 vis[i][j][k][l][o]=1; 42 } 43 } 44 } 45 } 46 } 47 int ans[37],num=0; 48 while(n){ 49 if(vis[n][P][A][C][M]){ 50 P-=p[n]; 51 A-=a[n]; 52 C-=c[n]; 53 M-=m[n]; 54 ans[++num]=n-1; 55 }n--; 56 } 57 printf("%d ",num); 58 for(int i=num;i>=1;i--) 59 printf("%d ",ans[i]); 60 printf(" "); 61 return 0; 62 }