为什么01背包,上面的代码WA#5#9#10,下面的代码AC,两个的dp数组定义不太一样
for(int i=1;i<=n;i++) weight[i]=w[i],value[i]=t[i]-w[i]*x;
for(int j=0;j<=W;j++)
{
if(j<=weight[1]) dp[j]=value[1];
else dp[j]=-1000000000000000000;
}
for(int i=2;i<=n;i++)
for(int j=W;j>=0;j--)
{
if(j<weight[i]) dp[j]=max(dp[j],dp[0]+value[i]);
else dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);
}
return dp[W]>0;
for(int j=0;j<=W;j++) dp[j]=-INF;
dp[0]=0;
for(int i=1;i<=n;i++)
for(int j=W;j>=0;j--)
{
int k=weight[i]+j;
if(k>W) dp[W]=max(dp[W],dp[j]+value[i]);
else dp[k]=max(dp[k],dp[j]+value[i]);
}