背包类型：
- 1.01背包问题
- 2.完全背包问题
- 3.多重背包问题
- 4.分组背包问题
- 5.二维背包
1.01背包问题
问题描述
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤1000
0<vi,wi≤1000
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例：
8
分析
对于本题我们不妨记
$$f[i][j]$$
表示只看前i个物品，总体积是j的情况下，总价值最大是多少？
首先根据题目分析可以知道,每件物品只有不选或者选两种情况,记为0和1:
$$①f[i][j]=f[i-1][j]$$
$$②f[i][j]=f[i-1][j-v[i]]+w[i]$$
其中第一个式子为不选第i个物品,第二个式子为选第i个物品。
对每一种情况都进行一次记录其最大值,即
$$f[i][j]=max{(①,②)}$$
根据以上分析可知
$$result=max(f[n],[0 \sim V])$$
代码
1 |
|
当然这个题不必把每一层的值都记下来,因此本题使用一维数组来对上面的方法进行优化。
虽说我们并没有将每一层的值都记录下来，但是我们再每一次循环的时候都会将每一行的值进行更新替换。
对此，如果我们还想使用上一行的值的话，只能通过从后往前进行更新了。
1 |
|
2.完全背包问题
问题描述
有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。
第 i 种物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 种物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤1000
0<vi,wi≤1000
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例：
10
分析
同01背包,我们不妨记f[i]表示为总体积是i的情况下,最大价值是多少。
其结果为
$$result =max(f[0 … m])$$
实际上在01背包中的第二个代码中，我们仅需把第二个循环中的内层循环顺序做修改即可，即
1 | for(int j=v[i];j<=m;j++) |
关于循环反过来正确的证明如下:
1.对于第一个物品考虑来说自然有
$$f[1]=2,f[2]=4,f[3]=6,f[4]=8,f[5]=10$$
显然是正确的
2.假设考虑前i-1个物品之后，所有的f[j]都是正确的。
3.来证明：在前i个物品中,所有的f[j]也都是正确的,
不妨固定某一个j,如果最优解包含了k个v[i],则一定会在循环内有
$$\displaystyle f[j-k\cdot v[i]]=max(f[j-k\cdot v[i]],f[j-k\cdot v[i]-v[i]]+w[i])$$
且一定会枚举到
$$f[j-k*v[i]]$$
其中
$$f[j-k*v[i]]$$
为前i-1个物品的值
$$f[j-k*v[i]-v[i]]$$
为前i个物品的值
无论如何,最后都会传递到
$$max(f[v[i]],f[0]+w[i])$$
由2可知
$$f[j]都是正确的\Rightarrow f[v[i]]也一定都是正确$$
又
$$f[0]=0$$
那么
$$w[i]一定正确\Rightarrow \max(f[v[i],f[0]+w[i]])一定正确\Rightarrow f[j-k*v[i]] 一定正确 \Rightarrow f[j]一定正确$$
以上,得证
代码
1 |
|
3.多重背包问题(easy)
问题描述
有 n 种物品要放到一个袋子里，袋子的总容量为 m，第 i 种物品的体积为 vi，把它放进袋子里会获得 wi 的收益，一共有 li 个。问如何选择物品，使得在物品的总体积不超过 m 的情况下，获得最大的收益？请求出最大收益。
数据范围
$$1\leq n, m, v_i, w_i, l_i \leq 100$$
分析
第 i 种物品可以使用 li 次， 我们可以把它拆成 Ii个物品，每个物品只可以用一次。即转换成01背包问题。
代码
1 |
|
4.多重背包问题(medium)
与easy版本不同的是：该题的数据范围更大了。
问题描述
有 n 种物品要放到一个袋子里，袋子的总容量为 m，第 i 种物品的体积为 vi，把它放进袋子里会获得 wi 的收益，一共有 li 个。问如何选择物品，使得在物品的总体积不超过 m 的情况下，获得最大的收益？请求出最大收益。
数据范围
$$1\leq n, m, v_i, w_i, l_i \leq 2000$$
分析
通过二进制拆分的方法可以优化本题。
令 m 为最大的 i 满足 $$2^{i + 1} - 1 \leq n$$ , 我们从 $$1, 2, 4, 8, 16, \cdots ,2 ^ m, n - 2^{m + 1} + 1$$ 中选一些数字相加，就可以得出任意 [0,n] 内的值，每个数字只能用一次。
引理：从$$1,2,\cdots,2^m$$ 中选一些数字相加，可以得出任意$$[0,2^{m + 1})$$ 内的值，每个数字只能用一次。
用数学归纳法进行证明：
当 m = 0 的时候显然是成立的；
假设当 m = k 时也成立，也就是从$$1,2,\cdots,2^k$$ 中选一些数字相加，可以得出任意 $$[0,2^{k + 1})$$ 内的值；
不难知道 对$$[0,2^{k + 2})$$ 内的值可以从 $$1,2,\cdots,2^k$$ 中选一些数字相加得到；
也就是说对任意 m = k + 1 也成立。
同样：对于在$$[2^{m + 1},n]$$ 内的值，我们取$$n - 2^{m + 1} + 1$$ 后，剩下的数字在$$[2^{m + 2} - n - 1,2^{m + 1})$$ 内，也可以从$$1,2,\cdots,2^m$$中选一些数字相加得到。
而通过以上的操作，我们可以把它拆成 O(log n) 个物品，每个物品只能用一次。
代码
1 |
|
5.多重背包问题(hard)
与easy和medium版本不同的是：该题的数据范围更大了。
问题描述
有 n 种物品要放到一个袋子里，袋子的总容量为 m，第 i 种物品的体积为 vi，把它放进袋子里会获得 wi 的收益，一共有 li 个。问如何选择物品，使得在物品的总体积不超过 m 的情况下，获得最大的收益？请求出最大收益。
数据范围
$$1\leq n, m, v_i, w_i, l_i \leq 10000$$
分析
把考虑了前 i 组物品以后，总体积为 0~m 时的最大收益都记下来。
考虑了前 i 组物品， 总体积为 j 时分成两种情况：
Case 1： 第 i 组物品一个没取，问题就变成了考虑前 i - 1 组物品，总体积为 j 时的情况。
Case 2： 第 i 组物品取了， 我们枚举取了其中的物品 k ， 问题变成了考虑了前 i - 1 组物品， 总体积为 j - v_i * k 时的情况。
f[i] [j] 表示考虑了前 i 组物品，总体积为 j 时的最大收益。
转移为：$$\displaystyle f[i][j] = max(f[i - 1][j],\max_{1\leq k\leq min(\frac{j}{v_i},l_i)}f[i - 1][j - v_i * k] + w_i * k)$$
需对时间复杂度进行优化
在某一类下标 k 的位置，可以转移到下表在 [k + 1,k + l_i] 中的位置。
而下标 k，x 之间转移的时候，转移状态可以为：
$$\displaystyle \max_{k,1\leq k < x, x - k \leq l_i} (f[k] + (x - k) * w_i)$$
那么将 f[k] - k * w_i放进单调队列即可。
代码
1 |
|
6.分组背包
有 n 种物品要放到一个袋子里，袋子的总容量为 m。第 i 个物品属于第 ai 组，每组物品我们只能从中选择一个。第 i 种物品的体积为 vi，把它放进袋子里会获得 wi 的收益。问如何选择物品，使得在物品的总体积不超过 m 的情况下，获得最大的收益？请求出最大收益。
数据范围：
$$1\leq n, m, a_i, v_i, w_i \leq 1000$$
分析
把考虑了前 i 组物品以后，总体积为 0~m 时的最大收益都记下来。
考虑了前 i 组物品， 总体积为 j 时分成两种情况：
Case 1： 第 i 组物品一个没取，问题就变成了考虑前 i - 1 组物品，总体积为 j 时的情况。
Case 2： 第 i 组物品取了， 我们枚举取了其中的物品 k ， 问题变成了考虑了前 i - 1 组物品， 总体积为 j - v_k 时的情况。
f[i] [j] 表示考虑了前 i 组物品，总体积为 j 时的最大收益。
代码
1 |
|
优化代码
1 |
|
7.二维背包
有 n 种物品要放到一个袋子里，袋子的总容量为 m，我们一共有 k 点体力值。第 i 种物品的体积为 vi，把它放进袋子里会获得 wi 的收益，并且消耗我们 ti 点体力值，每种物品只能取一次。问如何选择物品，使得在物品的总体积不超过 m 并且花费总体力不超过 k 的情况下，获得最大的收益？请求出最大收益。
数据范围：
$$1\leq n, m, k, a_i, v_i, w_i \leq 100$$
分析
相较于分组背包就是多了一个体力限制。
把考虑了前 i 组物品以后，总体积为 0~m ，总体力为 0~k 时的最大收益都记下来。
考虑了前 i 组物品， 总体积为 j，总体力为 x 时分为两种情况：
Case 1： 第 i 组物品一个没取，问题就变成了考虑前 i - 1 组物品，总体积为 j 时，总体力为 x 时的情况。
Case 2： 第 i 组物品取了， 我们枚举取了其中的物品 k ， 问题变成了考虑了前 i - 1 组物品， 总体积为 j - v_k ，总体力为 x - t_i 时的情况。
f[i] [j] [x] 表示考虑了前 i 组物品，总体积为 j ，总体力为 x 时的最大收益。
代码
1 |
|
优化：
1 |
|