poj 1742 多重背包

虽然说这题多重背包很明显，但是没有花一点时间是过不了的，TLE 了n次啊，一开始直接用 多重背包 做法直接上，结果T了，后来也看了一些别人的做法，真的是需要思考啊。。

因为这题是判断最后 是否 符合条件，因此没必要 记录 最优结果，因此只要 利用 bool （int就 TLE，各种yy）记录是否 满足条件就可以了。

在 01 背包中，dp[i]=dp[i]|dp[i-cost]，表示i的状态要么由 本身 或者  i-cost 推过来，本来是 dp[i]=max(dp[i],dp[i-cost]+weight),但是这边没必要了。。

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;

const int maxV=100005;
const int maxn=105;
int c[maxn],w[maxn];
int n,V;
bool dp[maxV];

void ZeroOnePack(int cost){
	for(int i=V;i>=cost;i--)dp[i]|=dp[i-cost];
}

void CompletePack(int cost){
	for(int i=cost;i<=V;i++)dp[i]|=dp[i-cost];
}

void MultiplePack(int cost,int amount){
	if(cost*amount>=V)CompletePack(cost);
	else {
		int k=1;
		while(k<amount){
			ZeroOnePack(k*cost);
			amount-=k;
			k<<=1;
		}
		ZeroOnePack(amount*cost);
	}
}

int main(){

	while(scanf("%d%d",&n,&V)&&(n||V)){
			for(int i=1;i<=n;i++)scanf("%d",w+i);
			for(int i=1;i<=n;i++)scanf("%d",c+i);

			//memset(dp,0,sizeof(dp));
			for(int i=0;i<=V;i++)dp[i]=0;
			dp[0]=1;
			for(int i=1;i<=n;i++){
				if(c[i])MultiplePack(w[i],c[i]);
			}
			int ans=0;
			for(int i=1;i<=V;i++)if(dp[i])ans++;
			printf("%d\n",ans);
		}
		return 0;

}

更多详细信息请查看java教程网 http://www.itchm.com/forum-59-1.html