Uva624 01背包输出方案 xingxing在努力
题目是给你一个长度为N的磁带， 让你将t首歌放入磁带中， 输出歌曲总长度不超过N的情况下的方案。
代码如下：
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; int c[30]; int f[10000 + 100]; int vis[30][10000 + 10]; int n, m; int main() { while(scanf("%d%d", &n, &m) == 2) { for(int i=1; i<=m; i++) scanf("%d", &c[i]); memset(f, 0, sizeof(f)); memset(vis, 0, sizeof(vis)); for(int i=m; i>=1; i--) { for(int j=n; j>=c[i]; j--) { if(f[j] < f[j-c[i]]+c[i]) { f[j] = f[j-c[i]] + c[i]; vis[i][j] = 1; } } } for(int i=1, j=f[n]; i<=m; i++) if(vis[i][j]) { printf("%d ", c[i]); //printf("%d %d ", i, j); j -= c[i]; } printf("sum:%d ", f[n]); } return 0; }