CD |
You have a long drive by car ahead. You have a tape recorder, but unfortunately your best music is on CDs. You need to have it on tapes so the problem to solve is: you have a tape N minutes long. How to choose tracks from CD to get most out of tape space and have as short unused space as possible.
Assumptions:
Program should find the set of tracks which fills the tape best and print it in the same sequence as the tracks are stored on the CD
5 3 1 3 4 10 4 9 8 4 2 20 4 10 5 7 4 90 8 10 23 1 2 3 4 5 7 45 8 4 10 44 43 12 9 8 2
1 4 sum:5 8 2 sum:10 10 5 4 sum:19 10 23 1 2 3 4 5 7 sum:55 4 10 12 9 8 2 sum:45
解题思路:path[i][j]记录策略的选择,输出的时候倒推回去
#include <iostream> #include <cstdio> #include <cstring> #define N 10005 using namespace std; int main() { int m,n,i,j; int dp[N],path[25][N],v[25]; //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); while(~scanf("%d%d",&n,&m)) { for(i=0;i<m;i++) scanf("%d",v+i); memset(dp,0,sizeof(dp)); memset(path,0,sizeof(path)); for(i=0;i<m;i++) for(j=n;j>=v[i];j--) if(dp[j]<dp[j-v[i]]+v[i]) { dp[j]=dp[j-v[i]]+v[i]; path[i][j]=1; } else path[i][j]=0; j=n; for(i=m-1;i>0;i--) { if(path[i][j]==1 && j>=0) { printf("%d ",v[i]); j-=v[i]; } } printf("sum:%d\n",dp[n]); } return 0; }
原文:http://blog.csdn.net/hqu_fritz/article/details/36446889