01背包问题
于 2022-03-15 发布
文件大小:255.10 kB
0 236
下载积分: 2
下载次数: 1
代码说明：
01背包是在M件物品取出若干件放在空间为W的背包里，每件物品的体积为W1，W2……Wn，与之相对应的价值为P1,P2……Pn。考虑用动态规划的方法来解决，这里的：阶段是：在前N件物品中，选取若干件物品放入背包中； 状态是：在前N件物品中，选取若干件物品放入所剩空间为W的背包中的所能获得的最大价值；决策是：第N件物品放或者不放； 由此可以写出动态转移方程：我们用f[i,j]表示在前 i 件物品中选择若干件放在所剩空间为 j 的背包里所能获得的最大价值f[i, j] = max( f[i-1, j-Wi] + Pi (j >= Wi), f[i-1, j] )
下载说明：请别用迅雷下载，失败请重下，重下不扣分！
发表评论
