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;}