0002

2. 01背包问题

题目

有 $N$ 件物品和一个容量是 $V$ 的背包。每件物品只能使用一次。

第 $i$ 件物品的体积是 $v_i$，价值是 $w_i$。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

输出最大价值。

输入格式

第一行两个整数，$N，V$，用空格隔开，分别表示物品数量和背包容积。

接下来有 $N$ 行，每行两个整数 $v_i, w_i$，用空格隔开，分别表示第 $i$ 件物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

$0 \lt N, V \le 1000$

$0\lt v_i, w_i \le 1000$

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例：

8

题解

前置题目：0000

前置知识：无

本题知识：动态规划-背包问题

题目分析

题目条件：从前 N 件物品中选择任意件物品使得总体积小于等于 V

题目的解：在满足题目条件的所有元素中计算出最大价值是多少

从前 N 件物品中选择任意件物品使得总体积小于等于 V，在这个集合中的具有最大价值的元素，也即是题目的解有且只有两种可能性：

1. 没有选择第 N 件物品
   • 即从前 N - 1 件物品中选择任意件物品使得总体积小于等于 V，在这个集合中的具有最大价值的元素
2. 选择了第 N 件物品
   • 有一点思维含量，需要思路转换
   • 第 N 件物品是我们必须要选择的
   • 即从前 N - 1 件物品中选择任意件物品使得总体积小于等于 V - V_N，在这个集合中的具有最大价值的元素
   • 总价值 = 该元素的最大价值 + 第 N 件物品的价值

题目的解就是两种可能性中的最大价值

具象到抽象

设集合(i, j)表示题目条件，即只从前 i 个物品中选择且总体积小于等于 j

设函数f表示在集合中选择最大价值

f(i, j) = Max(f(i-1, j), f(i-1, j-v_i) + w_i)

所以f(N, V)即是题目的解

实现细节

• f(0, 0~j)因为没有选择物品，故值为0

• 边界条件检验：第二种可能性不一定存在，比如说 N 的体积已经超过允许范围

实现优化

因为在求f(i, ?)的时候只用到了f(i-1, ?)，所以可以使用滚动数组来节省空间

使得二维数组降到一维数组

f(j) = Max(f(j), f(j-v_i) + w_i)

不过要注意状态的保护，f(j-v_i)是在 i - 1 层计算得到的，

所以如果循环是从小到大的计算到f(j)时f(j-v_i)的值就已经是第 i 层的，i - 1层的数据已经丢失。

解决方法很简单，只需要将遍历顺序修改为从大到小，此时计算到f(j)时f(j-v_i)的值还未被覆盖，仍是第 i - 1层的数据。