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