动态规划－0-1背包问题的自我理解

作者: JLGao的简书 | 来源:发表于2021-11-20 15:19 被阅读0次

动态规划
初识动态规划
Algorithm进阶计划 -- 动态规划（下）
数据结构与算法笔记day23：动态规划
算法-动态规划-背包问题
背包问题
背包问题
Algorithm
算法3：动态规划
动态规划-0-1背包问题

动态规划的定义不明白的小伙伴自己动手百度吧，这里不再重述，我们直接切入正题。

0-1背包问题：假设有一个背包，其容量为 $capacity$ 。在地上有一堆物品，其数量为 $n$ ，每个物品有两种属性：重量 $w$ 和价值 $v$ ，那么我们就会想到这样的一个优化问题：
$obj. max\sum_{i\epsilon N}v_{i}; \ \ \ \ cons. \sum_{i\epsilon N}w_{i}\leq capacity$
即，找到一个物品的组合，使得它们的重量小于等于背包最大容量，并且价值最大。

举例：现有一个背包，容量 $capacity=8$ ，物品的个数 $n=4$ ，每个物品的重量 $w=\left \{2,3,4,5\right \}$ ，价值 $v=\left \{3,4,5,6\right \}$ 。
我们分两步确定：确定背包可以装物品的最大价值、确定背包中物品的组合。

1、确定背包可以装物品的最大价值

现在我们给出一个表格 $dp$ 记录每个状态下，背包中物品的最大价值。表格中的行 $i=\left \{0,1,2,3,4\right \}$ ，表示第 $i$ 件物品；表格中的列 $j=\left \{0,1,2,3,4,5,6,7,8\right \}$ ，表示背包中的剩余容量。表格中第 $i$ 行，第 $j$ 列中元素 $dp[i][j]$ 表示的含义是：拿第 $i$ 件物品，剩余容量 $j$ 下的最大价值。

(1) $i=0$ ，不拿物品。背包可能有两种状态：背包是空的、塞满没有价值的东西。这时， $dp[0][j]=0,\ j\epsilon \left \{0,1,2,3,4,5,6,7,8\right \}$ ；

$dp$	0	1	2	3	4	5	6	7	8
0	0	0	0	0	0	0	0	0	0

(2) $j=0$ ，背包中没有剩余容量。背包塞满没有价值的东西。这时， $dp[i][0]=0,\ i\epsilon \left \{0,1,2,3,4\right \}$ ；

$dp$	1	2	3	4	5	6	7	8
0	0	0	0	0	0	0	0	0
1
2
3
4

(3) $i=1$ ，拿第一件物品，重量 $w[1]=2,\ v[1]=3$ 。背包可能有三种状态：背包是空的、装了一部分没有价值的东西、塞满没有价值的东西。这时，我们需要判断背包剩余容量 $j$ 和 $w[i]$ 的关系计算 $dp[i][j]$ ：

当 $j<w[1]=2$ 时，即背包中的剩余容量放不下这个物品，背包中的价值为上一个状态中背包中的价值，有 $dp[i][j]=dp[i-1][j]$ 。

$dp$	1	2	3	4	5	6	7	8
0	0	0	0	0	0	0	0	0
1	0
2
3
4

当 $j\geq w[1]=2$ 时，即背包中的剩余容量可以这个物品，所以将这件物品放进背包后，背包剩余容量 $j-w[i]$ 的价值 $dp[i][j]=dp[i-1][j-w[i]]+v[i]$ 。
$dp[1][2]=dp[0][2-2]+3=3,\cdots ,dp[1][8]=dp[0][8-2]+3=3$

$dp$	1	2	3	4	5	6	7	8
0	0	0	0	0	0	0	0	0
1	0	3	3	3	3	3	3	3
2
3
4

(4) $i=2$ ，拿第二件物品，重量 $w[2]=3,\ v[2]=4$ 。背包可能有三种状态：背包是空的、装了一部分没有价值的东西、塞满没有价值的东西。这时，我们需要判断背包剩余容量 $j$ 和 $w[i]$ 的关系计算 $dp[i][j]$ ：

当 $j<w[2]=3$ 时，即背包中的剩余容量放不下这个物品，背包中的价值为上一个状态中背包中的价值，有 $dp[i][j]=dp[i-1][j]$ 。

$dp$	1	2	3	4	5	6	7	8
0	0	0	0	0	0	0	0	0
1	0	3	3	3	3	3	3	3
2	0	3
3
4

当 $j\geq w[2]=3$ 时，即背包中的剩余容量可以放下这个物品，所以将这件物品放进背包后，背包剩余容量 $j-w[i]$ 的价值 $dp[i][j]=dp[i-1][j-w[i]]+v[i]$ 。
$dp[2][3]=dp[1][3-3]+4=4,\cdots ,dp[2][8]=dp[1][8-3]+4=7$

$dp$	1	2	3	4	5	6	7	8
0	0	0	0	0	0	0	0	0
1	0	3	3	3	3	3	3	3
2	0	3	4	4	7	7	7	7
3
4

(5) $i=3$ ，拿第三件物品，重量 $w[3]=4, \ v[3]=5$ 。背包可能有三种状态：背包是空的、装了一部分没有价值的东西、塞满没有价值的东西。这时，我们需要判断背包剩余容量 $j$ 和 $w[i]$ 的关系计算 $dp[i][j]$ ：

当 $j<w[3]=4$ 时，即背包中的剩余容量放不下这个物品，背包中的价值为上一个状态中背包中的价值，有 $dp[i][j]=dp[i-1][j]$ 。

$dp$	1	2	3	4	5	6	7	8
0	0	0	0	0	0	0	0	0
1	0	3	3	3	3	3	3	3
2	0	3	4	4	7	7	7	7
3	0	3	4
4

当 $j\geq w[3]=4$ 时，即背包中的剩余容量可以放下这个物品，所以将这件物品放进背包后，背包剩余容量 $j-w[i]$ 的价值 $dp[i][j]=dp[i-1][j-w[i]]+v[i]$ 。
$dp[3][4]=dp[2][4-4]+5=5$
$dp[3][5]=dp[2][5-4]+5=5$
$dp[3][6]=dp[2][6-4]+5=8$
$dp[3][7]=dp[2][7-4]+5=9$
$dp[3][8]=dp[2][8-4]+5=9$

$dp$	1	2	3	4	5	6	7	8
0	0	0	0	0	0	0	0	0
1	0	3	3	3	3	3	3	3
2	0	3	4	4	7	7	7	7
3	0	3	4	5	5	8	9	9
4

观察表格，发现 $dp[3][5]<dp[2][5]$ ，为什么？ $j=5$ ，我们应该怎么拿商品才能使得剩余容量的价值最大？

如果拿第三件物品，背包中剩余容量为 $j-w[3]=5-4=1$ ，我们怎样计算容量为1时怎样那物品才能使背包中物品价值最大？那么这就追溯到前一个状态，就是拿第二件物品时，剩余容量 $j-w[3]=1$ 时的最大价值 $dp[i-1][j-w[3]]$ 。所以， $dp[3][5]=dp[i-1][j-w[i]]+v[i]=dp[2][5-4]+5=5$ 。
如果不拿第三件物品，背包中剩余容量为 $j=5$ ，那么这就追溯到前一个状态，就是拿第二件物品时， $j=5$ 时的价值 $dp[i-1][j]$ 。所以， $dp[3][5]=dp[i-1][j]=dp[2][5]=7$ 。
由此，我们知道，当背包中剩余容量为 $5$ 时，拿两件（第一件和第二件）物品( $value=7$ )比只拿第三件( $value=5$ )物品的价值大。

总结一下，当我们考虑是否拿第 $i$ 件物品时，剩余容量 $j$ 的最大价值 $dp[i][j]$ 的计算为：
$dp[i][j]=\left\{\begin{matrix} dp[i-1][j], &j<w[i] \\ max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]), & j\geqslant w[i] \end{matrix}\right.$

以上公式就是0-1背包问题的状态转移方程。根据这个状态转移方程，我们重新计算和更新一下 $dp$ 表格。

$dp$	1	2	3	4	5	6	7	8
0	0	0	0	0	0	0	0	0
1	0	3	3	3	3	3	3	3
2	0	3	4	4	7	7	7	7
3	0	3	4	5	7	8	9	9
4

(6) $i=4$ ，拿第四件物品，重量 $w[4]=5, \ v[4]=6$ 。 $dp$ 表格的更新自己动手计算一下吧，验证一下你对0-1背包问题的理解。这里给出最终的表格。

$dp$	2	3	4	5	6	7	8
0	0	0	0	0	0	0	0
1	3	3	3	3	3	3	3
2	3	4	4	7	7	7	7
3	3	4	5	7	8	9	9
4	3	4	5	7	8	9	10

2、确定背包中物品的组合

根据状态转移方程，得到物品组合。
(1) $dp[4][8]=max(dp[3][8],\ dp[3][8-w[4]]+v[4])=dp[3][8-w[4]]+v[4]$ ，可以知道物品组合中有第四件物品。除去第四件物品，剩余物品组合所占的容量为 $8-w[4]=8-5=3$ ，价值为 $10-v[4]=10-6=4$ ；
(2) $3-w[3]=3-4<0$ ，所以没有拿第三件物品， $dp[3][3]=dp[2][3]$ ；
(3) $dp[2][3]=max(dp[1][3],\ dp[1][3-w[1]]+v[2])=dp[1][3-w[1]]+v[2]$ ，可以知道物品组合中有第二件物品。除去第二件物品，剩余物品组合所占的容量为 $3-w[2]=3-3=0$ ，价值为 $4-v[2]=4-4=0$ .
所以，背包中装第二件物品和第四件物品可以得到最大价值。

以上是本人对0-1背包问题的理解，如有错误，欢迎留言纠正！

动态规划
0-1背包问题自己实现的0-1背包问题的动态规划解法，先贴上吧，动态规划原理解释有空再写。
初识动态规划
0-1 背包问题备忘录动态规划-二维数组动态规划-一维数组 0-1 背包问题升级版回溯算法动态规划-二维...
Algorithm进阶计划 -- 动态规划（下）
经典动态规划背包问题最长子序列问题 1. 背包问题 1.1 0-1 背包问题 0-1 背包问题，描述如下：上面...
数据结构与算法笔记day23：动态规划
1初识动态规划这节课的内容不涉及动态规划的理论，而是通过两个例子：0-1背包问题、0-1背包问题升级...
算法-动态规划-背包问题
背包问题是基础的动态规划问题，包含了0-1背包，完全背包，多重背包等。 0-1背包存在容量为的背包，件体...
背包问题
背包问题属于典型的动态规划问题。这里我们将详细介绍0-1背包，完全背包和多重背包问题一、 0-1背包有N件物品...
背包问题
1、前言背包问题是典型的动态规划问题，它有非常多的类型，本文讨论最常见的0-1背包问题 0-1背包问题描述：有一...
Algorithm
bit manipulation 动态规划 0-1背包问题寻找最小的k个数
算法3：动态规划
5.动态规划5.1 什么是动态规划？5.2 自底向上的动态规划：5.3 自顶向下的动态规划5.4 0-1背包问题：...
动态规划-0-1背包问题
动态规划-0-1背包问题动态规划（dynamic programming）是解决多阶段决策问题常用的最优化理论，...