背包问题(Knapsack Problem, KP)
是NP
完全问题,也是一类重要 的组合优化问题 ,在工业 、经济 、通信、金融与计算机 等领域的资 源分配 、 资金预算 、 投资决策 、 装载问题 、 整数规划 、 分布式系统 与密码系统中具有重要的理论和应用价值。
通俗说法
贼,夜入豪宅,可偷之物甚多,而负重能力有限,偷哪些才更加不枉此行?
抽象说法
给定一组多个())物品,每种物品都有自己的重量())和价值()),在限定的总重量/总容量()内,选择其中若干个(也即每种物品可以选0个或1个),设计选择方案使得物品的总价值最高。
更加抽象的说法
给定正整数)、给定正整数,求解0-1规划问题:
, s.t. , 。
0-1背包问题的递推关系
定义子问题 为:在前 个物品中挑选总重量不超过 的物品,每种物品至多只能挑选1个,使得总价值最大;这时的最优值记作 ,其中 , 。
考虑第 个物品,无外乎两种可能:选,或者不选。
- 不选的话,背包的容量不变,改变为问题 ;
- 选的话,背包的容量变小,改变为问题 。
最优方案就是比较这两种方案,哪个会更好些:
。
得到
。
“填二维表”的动态规划方法
时才会有“取第 件物品”发生。
所以从表格右下角“往回看”如果是“垂直下降”就是发生了 ,而只有“走斜线”才是“取了”物品。
这个算法的复杂度就很容易算了——每一个格子都要填写数字,所以时间复杂度和空间复杂度都是 。当” “时(就不严谨地使用渐近分析的语言了),复杂度是 。
手撕Java版本代码
1 | package com.cyblogs.algorithm; |
最后输出的结果是:26。
参考地址
如果大家喜欢我的文章,可以关注个人订阅号。欢迎随时留言、交流。如果想加入微信群的话一起讨论的话,请加管理员微信号:chengcheng222e
,他会拉你们进群。