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

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

uva 624 cd

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

#include<stdio.h>
#include<string.h>
#define maxn 10010
int n,w[maxn],m; //花费都是1
int 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;
}