UC知道0/1背包问题求助
来源：百度知道 编辑：UC知道 时间：2024/06/21 00:52:59
请写出状态转移方程，谢谢！最好附一点说明。
(1)在M件物品取出若干件放在空间为W的背包里，每件物品的重量为W1，W·2……Wn，与之相对应的价值为P1,P2……Pn。求出获得最大价值的方案。
(2)有一个箱子容量为v(正整数，o≤v≤20000)，同时有n个物品(o≤n≤30)，每个物品有一个体积 (正整数)。要求从 n 个物品中，任取若千个装入箱内，使箱子的剩余空间为最小。
有没有动态规划的解法？
(1)在M件物品取出若干件放在空间为W的背包里，每件物品的重量为W1，W·2……Wn，与之相对应的价值为P1,P2……Pn。求出获得最大价值的方案。
(2)有一个箱子容量为v(正整数，o≤v≤20000)，同时有n个物品(o≤n≤30)，每个物品有一个体积 (正整数)。要求从 n 个物品中，任取若千个装入箱内，使箱子的剩余空间为最小。
有没有动态规划的解法？
(1)设dp[i][j]为对第i件物品作决策后(选或不选),重量为j时可以取得的最大价值
则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}为所求