虽然说这题多重背包很明显,但是没有花一点时间是过不了的,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; }