uva 624 CD 01背包状态压缩记路径

uva 624 cd

要把cd上的音乐导到磁带里，要求尽量使磁带剩余的空间小并按顺序打印出每次磁带中的每个音轨长度。tracks不超过20，且按顺序输出，状态压缩记录路径。

#include<stdio.h>#include<string.h>#define maxn 10010int n,w[maxn],m; //花费都是1int dp[maxn];int state[maxn];int main(){int i,j,k,l,m;while(~scanf("%d",&n)){scanf("%d",&m);memset(dp,0,sizeof(dp));memset(state,0,sizeof(state));int r;for(i=0;i<m;i++){scanf("%d",&w[i]);r=1<<i;for(j=n;j>=w[i];j--){if(dp[ j-w[i] ]+w[i] >dp[j]){dp[j]=dp[ j-w[i] ]+w[i];state[j]=r|state[j-w[i]];  //状态也更新}}}for(i=0;i<m;i++){r=1<<i;if(r&state[n])printf("%d ",w[i]);}printf("sum:%d\n",dp[n]);}return 0;}