求助01背包dp细节,有注释
查看原帖
求助01背包dp细节,有注释
482856
TigerNick楼主2024/5/26 14:57

为什么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;
	// 定义:dp[i][j]:表示在前 i 个物品内取,总重>=j时的最大价值 
	for(int j=0;j<=W;j++)
	{
		if(j<=weight[1]) dp[j]=value[1];
		else dp[j]=-1000000000000000000;
	}// n==1时的边界处理 
	
	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]);// j-weight[i]<0 时视作 0 
			else dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);
		}
	return dp[W]>0;
//定义:dp[i][j]表示前i个物品,总重等于j时的最大价值(总重大于W时视作W)
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]);
		}
2024/5/26 14:57
加载中...