0/1背包问题求助
发布网友
发布时间：2023-12-29 17:03
共1个回答
热心网友
时间：2024-03-19 00:10
则dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+p[i])
注意下标的计算,别越界了.
dp[n]中的最大值为所求.
(2)设dp[i][j]为对第i件物品作决策后(选或不选),容量为j的可能性(如0为不可能,1为可能)
则dp[i][j]=dp[i-1][j]||dp[i-1][j-v[i-1]]
同样注意下标的计算.
dp[n]即表示所有剩余容量的可能性
max{i,dp[i]==1}为所求
