0-1背包问题Knapsack Problem
背包问题(Knapsack Problem, KP)是NP完全问题，也是一类重要 的组合优化问题 ，在工业 、经济 、通信、金融与计算机 等领域的资 源分配 、 资金预算 、 投资决策 、 装载问题 、 整数规划 、 分布式系统 与密码系统中具有重要的理论和应用价值。
通俗说法
贼，夜入豪宅，可偷之物甚多，而负重能力有限，偷哪些才更加不枉此行？
抽象说法
给定一组多个（
）物品，每种物品都有自己的重量（
）和价值（
），在限定的总重量/总容量（
）内，选择其中若干个（也即每种物品可以选0个或1个），设计选择方案使得物品的总价值最高。
更加抽象的说法
给定正整数
、给定正整数
，求解0-1规划问题：
， s.t.
，
。
0-1背包问题的递推关系
定义子问题
为：在前
个物品中挑选总重量不超过
的物品，每种物品至多只能挑选1个，使得总价值最大；这时的最优值记作
，其中
，
。
考虑第
个物品，无外乎两种可能：选，或者不选。
- 不选的话，背包的容量不变，改变为问题
；
- 选的话，背包的容量变小，改变为问题
。
最优方案就是比较这两种方案，哪个会更好些：
。
http://static.cyblogs.com/v2-1d8090c991ca13cee3cb43c027b72304_1440w.jpg
得到
。
“填二维表”的动态规划方法
时才会有“取第
件物品”发生。
所以从表格右下角“往回看”如果是“垂直下降”就是发生了
，而只有“走斜线”才是“取了”物品。
http://static.cyblogs.com/v2-7bd4c72ec3b5f104e4db3c4aad98cc66_1440w.png
这个算法的复杂度就很容易算了——每一个格子都要填写数字，所以时间复杂度和空间复杂度都是
。当"
"时（就不严谨地使用渐近分析的语言了），复杂度是
。
手撕Java版本代码
package com.cyblogs.algorithm;
/**
* Created with leetcode-cn
*
* @description: 0-1 背包问题
* @author: chenyuan
* @date: 2021/3/29
* @time: 10:23
*/
public class Knapsack {
public static void main(String[] args) {
int N = 6, W = 21;
// 重量
int[] w = {0, 2, 3, 4, 5, 9};
// 价值
int[] v = {0, 3, 4, 5, 8, 10};
// 重量 * 价值
int[][] B = new int[N][W];
int k,C;
for (k = 1; k < N; k++) {
for (C = 1; C < W; C++) {
if (w[k] > C) {
B[k][C] = B[k-1][C];
} else {
// 装进书包
int value1 = B[k-1][C-w[k]] + v[k];
// 不装进书包
int value2 = B[k-1][C];
if (value1 > value2) {
B[k][C] = value1;
} else {
B[k][C] = value2;
}
}
}
}
System.out.println(B[5][20]);
}
}
最后输出的结果是：26。
参考地址
- https://www.bilibili.com/video/BV1U5411s7d7?t=1899
- https://zhuanlan.zhihu.com/p/30959069
如果大家喜欢我的文章，可以关注个人订阅号。欢迎随时留言、交流。如果想加入微信群的话一起讨论的话，请加管理员微信号：chengcheng222e，他会拉你们进群。
腾讯云开发者
