01背包问题一直是笔试题中的高频部分，看到一篇博客讲解的很详细，贴上来跟大家分享下，并说下自己的理解。自己另外加的部分已下划线标记，个人认为重要的部分加粗标记，方便理解。并附带了Python实现。
原博地址：https://blog.csdn.net/qq_38410730/article/details/81667885
另外，这几个链接也值得一看：
https://blog.csdn.net/xp731574722/article/details/70766804 0-1背包推导
https://github.com/CyC2018/CS-Notes/blob/master/notes/Leetcode%20%E9%A2%98%E8%A7%A3%20-%20%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92.md#0-1-%E8%83%8C%E5%8C%85 cyc大佬的leetcode习题集
问题描述
有n个物品，它们有各自的体积和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？
面对每个物品，我们只有选择拿取或者不拿两种选择，不能选择装入某物品的一部分，也不能装入同一物品多次。称为01背包问题，此外还有多重背包与完全背包问题。
为方便讲解和理解，下面讲述的例子均先用具体的数字代入，即：eg：number＝4，capacity＝8
i（物品编号） 1 2 3 4
w（体积） 2 3 4 5
v（价值） 3 4 5 6
根据动态规划解题步骤（问题抽象化、建立模型、寻找约束条件、判断是否满足最优性原理、找大问题与小问题的递推关系式、填表、寻找解组成）找出01背包问题的最优解以及解组成，然后编写代码实现。
动态规划的原理
动态规划与分治法类似，都是把大问题拆分成小问题，通过寻找大问题与小问题的递推关系，解决一个个小问题，最终达到解决原问题的效果。但不同的是，分治法在子问题和子子问题等上被重复计算了很多次，而动态规划则具有记忆性，通过填写表把所有已经解决的子问题答案纪录下来，在新问题里需要用到的子问题可以直接提取，避免了重复计算，从而节约了时间，所以在问题满足最优性原理之后，用动态规划解决问题的核心就在于填表，表填写完毕，最优解也就找到。
最优性原理是动态规划的基础，最优性原理是指“多阶段决策过程的最优决策序列具有这样的性质：不论初始状态和初始决策如何，对于前面决策所造成的某一状态而言，其后各阶段的决策序列必须构成最优策略”。
背包问题的解决过程
在解决问题之前，为描述方便，首先定义一些变量：Vi表示第 i 个物品的价值，Wi表示第 i 个物品的体积，定义V(i,j)：当前背包容量 j，前 i 个物品最佳组合对应的价值，同时背包问题抽象化（X1，X2，…，Xn，其中 Xi 取0或1，表示第 i 个物品选或不选）。
此处要注意各个变量代表的含义，尤其是V(i,j)：当前背包容量 j，前 i 个物品最佳组合对应的价值。
1、建立模型，即求max(V1X1+V2X2+…+VnXn)；
2、寻找约束条件，W1X1+W2X2+…+WnXn<capacity；
3、寻找递推关系式，面对当前商品有两种可能性：
包的容量比该商品体积小，装不下，此时的价值与前i-1个的价值是一样的，即V(i,j)=V(i-1,j)；
还有足够的容量可以装该商品，但装了也不一定达到当前最优价值，所以在装与不装之间选择最优的一个，即V(i,j)=max｛V(i-1,j)，V(i-1,j-w(i))+v(i)｝。
其中V(i-1,j)表示不装，V(i-1,j-w(i))+v(i) 表示装了第i个商品，背包容量减少w(i)，但价值增加了v(i)；
由此可以得出递推关系式：
j<w(i) V(i,j)=V(i-1,j) （装不下i，因此不考虑）
j>=w(i) V(i,j)=max｛V(i-1,j)，V(i-1,j-w(i))+v(i)｝（装与不装选一个，装的时候的表达式）
这里需要解释一下，为什么能装的情况下，需要这样求解（这才是本问题的关键所在！）：
可以这么理解，如果要到达V(i,j)这一个状态有几种方式？
肯定是两种，第一种是第i件商品没有装进去，第二种是第i件商品装进去了。没有装进去很好理解，就是V(i-1,j)；装进去了怎么理解呢？如果装进去第i件商品，那么装入之前是什么状态，肯定是V(i-1,j-w(i))。由于最优性原理（上文讲到），V(i-1,j-w(i))就是前面决策造成的一种状态，后面的决策就要构成最优策略。两种情况进行比较，得出最优。
4、填表，首先初始化边界条件，V(0,j)=V(i,0)=0；
然后一行一行的填表：
如，i=1，j=1，w(1)=2，v(1)=3，有j<w(1)，故V(1,1)=V(1-1,1)=0；
又如i=1，j=2，w(1)=2，v(1)=3，有j=w(1),故V(1,2)=max｛ V(1-1,2)，V(1-1,2-w(1))+v(1) ｝=max｛0，0+3｝=3；
如此下去，填到最后一个，i=4，j=8，w(4)=5，v(4)=6，有j>w(4)，故V(4,8)=max｛ V(4-1,8)，V(4-1,8-w(4))+v(4) ｝=max｛9，4+6｝=10……
所以填完表如下图：
5、表格填完，最优解即是V(number,capacity)=V(4,8)=10。
代码实现
为了和之前的动态规划图可以进行对比，尽管只有4个商品，但是我们创建的数组元素由5个。
#include<iostream>
using namespace std;
#include <algorithm>
int main()
{
int w[5] = { 0 , 2 , 3 , 4 , 5 }; //商品的体积2、3、4、5
int v[5] = { 0 , 3 , 4 , 5 , 6 }; //商品的价值3、4、5、6
int bagV = 8; //背包大小
int dp[5][9] = { { 0 } }; //动态规划表
for (int i = 1; i <= 4; i++) {
for (int j = 1; j <= bagV; j++) {
if (j < w[i])
dp[i][j] = dp[i - 1][j];
else
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
}
}
//动态规划表的输出
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 9; j++) {
cout << dp[i][j] << ' ';
}
cout << endl;
}
return 0;
}
Python实现：
w= [0 , 2 , 3 , 4 , 5 ] #商品的体积2、3、4、5
v = [0 , 3 , 4 , 5 , 6 ] #商品的价值3、4、5、6
bagV = 8; #背包大小
dp = [[0 for i in range(9) ]for i in range(5)] #动态规划表 ，注意新建二维数组方法
for i in range (5):
for j in range(bagV+1):
if j < w[i]:
dp[i][j] = dp[i - 1][j];
else:
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
#动态规划表的输出
for i in range(5):
res = []
for j in range(9):
res.append(dp[i][j])
print(res) 输出为：
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 3, 3, 3, 3, 3, 3, 3]
[0, 0, 3, 4, 4, 7, 7, 7, 7]
[0, 0, 3, 4, 5, 7, 8, 9, 9]
[0, 0, 3, 4, 5, 7, 8, 9, 10]
与推导表相吻合。
背包问题最优解回溯
通过上面的方法可以求出背包问题的最优解，但还不知道这个最优解由哪些商品组成，故要根据最优解回溯找出解的组成，根据填表的原理可以有如下的寻解方式：
V(i,j)=V(i-1,j)时，说明没有选择第i 个商品，则回到V(i-1,j)；
V(i,j)=V(i-1,j-w(i))+v(i)时，说明装了第i个商品，该商品是最优解组成的一部分，随后我们得回到装该商品之前，即回到V(i-1,j-w(i))；
一直遍历到i＝0结束为止，所有解的组成都会找到。
就拿上面的例子来说吧：
最优解为V(4,8)=10，而V(4,8)!=V(3,8)却有V(4,8)=V(3,8-w(4))+v(4)=V(3,3)+6=4+6=10，所以第4件商品被选中，并且回到V(3,8-w(4))=V(3,3)；
有V(3,3)=V(2,3)=4，所以第3件商品没被选择，回到V(2,3)；
而V(2,3)!=V(1,3)却有V(2,3)=V(1,3-w(2))+v(2)=V(1,0)+4=0+4=4，所以第2件商品被选中，并且回到V(1,3-w(2))=V(1,0)；
有V(1,0)=V(0,0)=0，所以第1件商品没被选择。
代码实现
背包问题最终版详细代码实现如下：
#include<iostream>
using namespace std;
#include <algorithm>
int w[5] = { 0 , 2 , 3 , 4 , 5 }; //商品的体积2、3、4、5
int v[5] = { 0 , 3 , 4 , 5 , 6 }; //商品的价值3、4、5、6
int bagV = 8; //背包大小
int dp[5][9] = { { 0 } }; //动态规划表
int item[5]; //最优解情况
void findMax() { //动态规划
for (int i = 1; i <= 4; i++) {
for (int j = 1; j <= bagV; j++) {
if (j < w[i])
dp[i][j] = dp[i - 1][j];
else
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
}
}
}
void findWhat(int i, int j) { //最优解情况
if (i >= 0) {
if (dp[i][j] == dp[i - 1][j]) {
item[i] = 0;
findWhat(i - 1, j);
}
else if (j - w[i] >= 0 && dp[i][j] == dp[i - 1][j - w[i]] + v[i]) {
item[i] = 1;
findWhat(i - 1, j - w[i]);
}
}
}
void print() {
for (int i = 0; i < 5; i++) { //动态规划表输出
for (int j = 0; j < 9; j++) {
cout << dp[i][j] << ' ';
}
cout << endl;
}
cout << endl;
for (int i = 0; i < 5; i++) //最优解输出
cout << item[i] << ' ';
cout << endl;
}
int main()
{
findMax();
findWhat(4, 8);
print();
return 0;
}
Python实现：
w= [0 , 2 , 3 , 4 , 5 ] #商品的体积2、3、4、5
v = [0 , 3 , 4 , 5 , 6 ] #商品的价值3、4、5、6
bagV = 8; #背包大小
dp = [[0 for i in range(9) ]for i in range(5)] #动态规划表
item = [0]*5 #最优解情况
def findMax(): #动态规划
for i in range (5):
for j in range(bagV+1):
if j < w[i]:
dp[i][j] = dp[i - 1][j];
else:
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
def findWhat(i,j): #最优解情况
if i>=0:
if dp[i][j] == dp[i-1][j]:
item[i] = 0
findWhat(i-1,j)
elif j - w[i] >= 0 and dp[i][j] == dp[i - 1][j - w[i]] + v[i]:
item[i] = 1
findWhat(i-1,j-w[i])
def print1():
for i in range(5):
res = []
for j in range(9):
res.append(dp[i][j])
print(res)
print(item)
findMax()
findWhat(4,8)
print1()
输出结果：
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 3, 3, 3, 3, 3, 3, 3]
[0, 0, 3, 4, 4, 7, 7, 7, 7]
[0, 0, 3, 4, 5, 7, 8, 9, 9]
[0, 0, 3, 4, 5, 7, 8, 9, 10]
[0, 0, 1, 0, 1]
趁热打铁，再来一道01背包问题的变式：leetcode(416): ，解析参考评论区题解与https://blog.csdn.net/qq_26410101/article/details/80806463
题意：给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1:
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].
示例 2:
输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集. 解析：可以看成一个背包大小为sum/2的 0-1背包问题。
翻译：给定一个只包含正整数的非空数组。是否可以从这个数组中挑选出一些正整数，每个数只能用一次，使得这些数的和等于整个数组元素的和的一半。
dp[i][j] ：表示从数组的 [0, i] 这个子区间内挑选一些正整数，每个数只能用一次，使得这些数的和等于 j。
根据我们学习的 0-1 背包问题的状态转移推导过程，新来一个数，例如是 nums[i]，根据这个数可能选择也可能不被选择：
如果不选择 nums[i]，在 [0, i - 1] 这个子区间内已经有一部分元素，使得它们的和为 j ，那么 dp[i][j] = true；
如果选择 nums[i]，在 [0, i - 1] 这个子区间内就得找到一部分元素，使得它们的和为 j - nums[i] ，我既然这样写出来了，你就应该知道，这里讨论的前提条件是 nums[i] <= j。
以上二者成立一条都行。于是得到状态转移方程是：dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i]], (nums[i] <= j)
1：如果不考虑第i个元素，那么情况等于前i-1个元素的情况即dp[i-1][j]（前i-1个元素如果已经可以划分子集左，那么剩下的元素直接划分到另外一边即子集右即可）
2：如果考虑第i个元素，那么情况等于前i-1个元素的子集和加上第i个元素的和可以组成和j，j-nums[i]表示前i-1个元素可以组成和为j-nums[i]，那么加上第i个元素nums[i]，和即可j，可以组成子集。
这道题元素的背指的在左半边子集，不背指的在右半边子集，我们的目标是使得左半边子集的和等于总和的一半。这样思考才会和背包问题对应上。
于是按照 0-1 背包问题的模板，我们不难写出以下代码。
from typing import List
class Solution:
def canPartition(self, nums: List[int]) -> bool:
size = len(nums)
# 特判
if size == 0:
return False
# 特判，如果整个数组的和都不是偶数，就无法平分
s = sum(nums)
if s & 1 == 1:
return False
# 二维 dp 问题：背包的容量
target = s // 2
dp = [[False for _ in range(target + 1)] for _ in range(size)]
# 先写第 1 行：看看第 1 个数是不是能够刚好填满容量为 target
for i in range(target + 1):
dp[0][i] = False if nums[0] != i else True
# i 表示物品索引
for i in range(1, size):
# j 表示容量
for j in range(target + 1):
if j >= nums[i]:
dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i]]
else:
dp[i][j] = dp[i - 1][j]
return dp[-1][-1]
作者：liweiwei1419
链接：https://leetcode-cn.com/problems/two-sum/solution/0-1-bei-bao-wen-ti-xiang-jie-zhen-dui-ben-ti-de-yo/
京公网安备 11010502036488号