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
",ans);
		}
		return 0;

}