计算磁带能装下的最大音乐的时长。
0-1背包的变形,注意因为需要按从前往后的顺序打印路径,所以在分阶段DP时,需要从后往前。
代码如下:
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> using namespace std; const int Maxn = 20; int cd[Maxn], dp[Maxn*500]; bool vis[Maxn][Maxn*500]; int main() { #ifdef test freopen("input.txt", "r", stdin); #endif int n, m; while(scanf("%d%d", &n, &m) != EOF) { memset(dp, 0, sizeof(dp)); memset(vis, 0, sizeof(vis)); for(int i=0; i<m; ++i) scanf("%d", &cd[i]); dp[0] = 1; for(int i=m-1; i>=0; --i) // 相当于倒叙累加得imax for(int j=n; j>=cd[i]; --j) { if(dp[j-cd[i]]) { dp[j] = 1; vis[i][j] = 1; } } int imax = 0; for(int i=n; i>=0; --i) if(dp[i]) { imax = i; break; } for(int i=0, j=imax; i<m; ++i) // 才可以按j -= cd[i]正序打印出路径 if(vis[i][j]) { printf("%d ", cd[i]); j -= cd[i]; } printf("sum:%d\n", imax); } return 0; }