首页 > 浅说——九讲背包之01背包

浅说——九讲背包之01背包

所谓九讲,也就是:

0/1背包

0/1背包降维

完全背包

多重背包(二进制优化)

混合背包

二维费用背包

分组背包

有依赖的背包

背包的方案总数背包的具体方案路径

0/1背包:

[问题描述](经典)

有一个吝啬的地主,不愿意给工人付工钱,就从家里的物品中取出N个,对工人说, 你可以从这些物品中任意挑选,只要你的口袋装得下。
现在已知物品的总数量N,和工人的口袋大小M,及每种物品所占的空间wi,物品的价值vi。求出该背包能装载的最大价值。(物品不可以分,不考虑物品间的缝隙)
输入:
2    8
8    6
3    4 
5    4
3    3
输出:
16
有人说贪心 不就对了,是啊,当然不对。
贪心:先选单位空间能获得价值更大者
2:8
3:4
3:3
15
正确选择:
2 8
3 4
5 4
16
懂?
当然用深搜的dalao我就不说了,这明显是01背包嘛。
第一步:状态设想

总问题:N个物品,占用M个空间时所能获得的最大价值。

子问题:f[i,j] :前i个物品占用j个空间时能获得的最大价值。(背包惯用定义方式)

第二步:初步规划动规方程

 从某个中间状态思考来源

F[i][j]=……….设前面的任何决策都有答案了,当前决策?(来源法)

因为只有选和不选两种方案,所以f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]);(若不选,及前i-1个物品占j个空间的最大价值,f[i-1][j],

                                                                                                          若选,及前i-1个物品占j-w[i]个空间的最大价值,f[i-1][j-w[i]]

第三步:打表  验证、确定动规方程

转载于:https://www.cnblogs.com/mzyczly/p/11174542.html

更多相关:

  • 《你的背包》 词曲:松哥   二零二零年 在香格里拉的花坛 你与我 都蹲坐在一块 那个背包装满要报销的清单 还有老婆 给我的咸鸭蛋 你的背包 背到现在还没烂 却成为松哥的另一半 千金不换 都怪自坏习惯 扔掉书包一起去吃饭...