动态规划（一）：背包问题
动态规划：背包问题（01背包、完全背包、多重背包、分组背包）
AcWing2. 01背包问题
有 \(N\) 件物品和一个容量是 \(V\) 的背包。每件物品只能使用一次。 第 \(i\) 件物品的体积是 \(v_i\)，价值是 \(w_i\)。 求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。 输出最大价值。
输入格式
第一行两个整数，\(N，V\) ，用空格隔开，分别表示物品数量和背包容积。 接下来有 \(N\) 行，每行两个整数 \(v_i,w_i\) ，用空格隔开，分别表示第 \(i\) 件物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
\(0 < N,V ≤ 1000; 0 < vi,wi≤1000\)
输入样例 4 5 1 2 2 4 3 4 4 5 输出样例： 8
朴素版Code: f [i][j] 表示只从前 i 中选物品，且总体积小于 j 的最大价值. f [i][j] 可以分为两类： 第一类：不包含 i, 则转化成从1~（i- 1)中选物品， f[i][j] = f[ i - 1][j]. 第二类：包含i, 等价于从前 i - 1中选总体积小于 j - v[i] 的物品，最终价值再加上w[i].
#pragma once
#include
const int N = 1010;
int volume[N], worth[N]; //表示物品的体积和价值
int f[N]; //状态表示，表示在体积为N的情况下，从前i的物品中所有选法的最大价值
///
/// 普通版本
///
void nomal_zero_one()
{
int f[N][N];
int num, knapsack_problem; //num：物品数量，knapsack_volume:背包容量
std::cin >> num >> knapsack_problem;
// 状态表示：f[i][j] 表示所有只在前i个物品中选，并且提及小于等于j的选法的价值中的最大价值
// 状态计算：通过不重或不漏的划分集合，然后一步步计算出来每个状态的值
// 这里分为包含第i个物品和不包含第i个物品两类，则价值最大值为：
// max{f[i-1][j], f[i-1][j - volume[i]] + worth[i]}
for (int i = 1; i <= num; ++i)
for (int j = 0; j <= knapsack_problem; ++j)
{
// 包含第i个物品的选法
if (j >= volume[i]) f[i][j] = std::max(f[i - 1][j], f[i - 1][j - volume[i]] + worth[i]);
// 不包含第i个物品的选法
else f[i][j] = f[i - 1][j];
}
}
优化版Code：
f[i]只用到了f[i - 1],可以使用滚动数组的方式求解；且第二维的体积一直都是小于等于j的。 在第二层循环中，如果从小到大枚举求得的 f [j - v[i]]是第 i层的值，（由于j - v[i] < j, 所以f[j - v[i]]是会先被更新的）这里采用从大到小枚举就可以解决。
以案例为例：
N = 4, V = 5
v1 = 1, w1 = 2
v2 = 2, w2 = 4
v3 = 3, w3 = 4
v4 = 4, w4 = 5
// 状态表示：满足一定条件的所有集合的相应属性值, 这里是最大值
f[i][j] = max{f[i - 1][j], f[i - 1][j - v[i]] + w[i]};
//状态计算
i = 1
j = 5, v1 = 1, w1 = 2 //从大到小开始，这样用的都是上一次的f[j]
f[5] = max{f[5], f[5-1] + 2} = 2; //这里的f[5]用的是f[0][5]以及f[0][5 - 1], 应该是0，因为一个物品也没有选，本身也默认为零，所以正好, 下同，都是用的上一次的
j = 4, v1 = 1, w1 = 2
f[4] = max{f[4], f[4 - 1] + 2} = 2;
j = 3, v1 = 1, w1 = 2
f[3] = max{f[3], f[3 - 1] + 2} = 2;
j = 2, v1 = 1, w1 = 2
f[2] = max{f[2], f[2 - 1] + 2} = 2;
j = 1, v1 = 1, w1 = 2
f[1] = max{f[1], f[1 - 1] + 2} = 2; //这里的f[i][0]也是零，因为没有体积供选择，而正好也是默认为零
i = 2
j = 5, v2 = 2, w2 = 4 //从大到小开始，这样用的都是上一次的f[j]
f[5] = max{f[5], f[5 - 2] + 4} = 6; //这里的f[5]正好用的是f[1][5]以及f[1][5 - 1]，因为f[2][5]和f[2][5 - 2]的值还没有计算，所以只能用上一次的，下同
j = 4, v2 = 2, w2 = 4
f[4] = max{f[4], f[4 - 2] + 4} = 6;
j = 3, v2 = 2, w2 = 4
f[3] = max{f[3], f[3 - 2] + 4} = 6;
j = 2, v2 = 2, w2 = 4
f[2] = max{f[2], f[2 - 2] + 4} = 4;
------------------------------------------------------------------------
j = 1, v2 = 2, w2 = 4 //这里不用计算，因为体积j放不下物品i, 正好默认就是上一次的，即f[i -1][1],所以用虚线隔开一下
f[1] = f[1] = 2; //等价于f[2][1] = f[1][1] = 2;
下面的情况都包含在前两个的情况中，自己递推，不要偷懒, 这就是滚动数组的概念，我们只有一个f[j]数组，却是随着i的变化滚动着使用的，之所以能够这样优化，是由状态表示递推公式来决定的。
同理，Fibonacci数列的递推公式为d[i] = d[i - 1] + d[i - 2]; d[0] = 1, d[1] = 1; i从2开始，读者自己用滚动数组实现一下
// n--方式滚动数组实现，返回得是one, 巧妙得避开了临界值判断
class Solution {
public:
int fib(int n) {
int one = 0,two = 1;
int three;
while(n --) //这里用得是n--非常好用，不用判断临界值
{
three = one + two;
one = two, two = three;
}
return one; //one永远是上一次得three, 而我们又是从n--开始得，所以正好，非常巧妙得避开了边界判断
}
};
/*
//正常逻辑滚动数组实现，需要判断一下临界值
class Solution {
public:
int fib(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
int d[3] = {0, 1, 1};
for (int i = 2; i <= n; ++i)
{
d[2] = d[0] + d[1];
d[0] = d[1];
d[1] = d[2];
}
return d[2];
}
};
*/
#pragma once
#include
const int N = 1010;
int volume[N], worth[N]; //表示物品的体积和价值
int f[N]; //状态表示，表示在体积为N的情况下，从前i的物品中所有选法的最大价值
///
/// 使用滚动数组优化的版本
///
void zero_one_knapsack_problem()
{
int num, knapsack_volume; // num代表物品的数量，knapsack_volume代表背包的容量
std::cin >> num >> knapsack_volume;
// 初始化所有的f[1~i][0]都为0，因为没有提及，
// 由于我们默认为f[0] = 0，所以很合适
// 不用初始化
for (int i = 1; i <= num; ++i)
std::cin >> volume[i] >> worth[i]; //输入第i个物品的体积和价值
// 因为f[i][j] = max{f[i - 1][j], f[i - 1][j - volume[i]] + worth[i]}
for (int i = 1; i <= num; ++i)
for (int j = knapsack_volume; j >= volume[i]; --j)
//这里使用了滚动数组
// 而且j < volume[i]的情况不需要考虑了，一定就是f[i - 1][j]
// 这里的j是从大到小，所以f[j] 是用的上一个i的f[j] 和 f[j - volume[i]]
f[j] = std::max(f[j], f[j - volume[i]] + worth[i]); //选法分为选第i个以及不选第i个
std::cout << f[knapsack_volume] << std::endl;
}
AcWing 3. 完全背包问题
有 \(N\) 种物品和一个容量是 \(V\) 的背包，每种物品都有无限件可用。
第 \(i\) 种物品的体积是 \(v_i\)，价值是 \(w_i\)。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行两个整数，\(N，V\)，用空格隔开，分别表示物品种数和背包容积。
接下来有 \(N\) 行，每行两个整数 \(v_i,w_i\)，用空格隔开，分别表示第 \(i\) 种物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
\(0
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例：
10
朴素版Code：
#pragma once
#include
const int N = 1010;
int volume[N], worth[N];
int f[N][N]; // 这里不能设置成局部变量，否则会造成栈溢出
int f2[N]; //优化版本2用的
// 朴素版代码
void palin_version()
{
int num, knapsack_volume;
std::cin >> num >> knapsack_volume;
for (int i = 1; i <= num; ++i)
std::cin >> volume[i] >> worth[i];
for (int i = 1; i <= num; ++i)
// 这里要思考为什么从volume[i]开始是合适的，
// 如果要包含第i个物品，那么如果第i个物品的容量必须小于总容量knapsack_v
// 否则就不用计算了，默认是上一次的即f[i - 1][j]
for (int j = volume[i]; j <= knapsack_volume; ++j) //直接从volume[i]开始
for (int k = 0; k * volume[i] <= j; ++k)
// 如果包含第i个物品，需要观察包含多少个, 0个的时候就是f[i-1][j]
// 然后迭代比较，max里面的f[i][j]实际上就是f[i-1][j]，这一行代码
// 等价于
// f[i][j] = f[i - 1][j] ; //此时k = 0, 即不包含物品i
// f[i][j] = max{f[i][j], f[i - 1][j - v[i] * k] + k * w[i]} ; //k从1开始
// 这两行, 因为k = 0的时候，就是f[i - 1][j]，所以第一种的情况包含在
// 第二种之中
f[i][j] = std::max(f[i][j], f[i - 1][j - volume[i] * k] + k * worth[i]);
std::cout << f[num][knapsack_volume] << std::endl;
}
优化版Code：
本题可以优化为01背包问题朴素版类似的代码，不同的是本题中
\(f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);\)
最终还可以将其优化为一维数组 \(f[N]\).
#pragma once
#include
const int N = 1010;
int volume[N], worth[N];
int f[N][N]; // 这里不能设置成局部变量，否则会造成栈溢出
int f2[N]; //优化版本2用的
// 优化版本一
void complete_knapsack_optimize_one()
{
int num, knapsack_volume;
std::cin >> num >> knapsack_volume;
for (int i = 1; i <= num; ++i)
std::cin >> volume[i] >> worth[i];
// 状态转移方程等价优化
for (int i = 1; i <= num; ++i)
// 这里从volume[i]开始和上面一样
for (int j = volume[i]; j <= knapsack_volume; ++j) //这里要注意从volume[i]开始
// 这里做了个等价替换
// f[i][j] = max{f[i- 1][j], f[i - 1][j -v[i]] + w[i], f[i - 1][j - 2v[i]] + 2 * w[i], f[i - 1][j - v[i] * k] + k * w[i]}
// f[i][j - v] = max{ f[i-1][j - v], f[i - 1[[j- 2v[i]] + w[i], .........}
// 可以发现f[i][j] = max{f[i-1][j], f[i-1][j-v] + w}
f[i][j] = std::max(f[i - 1][j], f[i][j - volume[i]] + worth[i]);
std::cout << f[num][knapsack_volume] << std::endl;
}
// 优化版本二
void complete_knapsack_optimize_two()
{
int num, knapsack_volume;
std::cin >> num >> knapsack_volume;
for (int i = 1; i <= num; ++i)
std::cin >> volume[i] >> worth[i];
// 滚动数组优化
for (int i = 1; i <= num; ++i)
for (int j = volume[i]; j <= knapsack_volume; ++j)
// 滚动数组砍成一维， f2[j]还没有计算，只能是上一次点的f[i - 1][j]
// f2[j - v[i]] 由于j是从小到到大计算的，所以在第j次循环，j-vi已经计算完成
// 所以f2[j - v[i]] == f[i - 1][j - v[i]]
f2[j] = std::max(f2[j], f2[j - volume[i]] + worth[i]);
std::cout << f2[knapsack_volume] << std::endl;
}
LeetCode322 零钱兑换
给你一个整数数组 \(coins\) ，表示不同面额的硬币；以及一个整数 \(amount\) ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 \(-1\) 。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
示例 2：
输入：coins = [2], amount = 3
输出：-1
示例 3：
输入：coins = [1], amount = 0
输出：0
数据范围
\(
1 <= coins.length <= 12;
1 <= coins[i] <= 231 - 1;
0 <= amount <= 104
\)
思路：直接抽象成完全背包问题，物品有i个，硬币的面值是是体积，总体积也就是背包容量是amount, 每个硬币的价值也就是个数是1，这题让我们求得是在满足背包容量得情况下，最小得价值是多少；这样虽然有点拗口，如果不习惯也可以换着理解，只不过这样更符合背包得要求。
那么 \(f[i][j]\) 就表示从前i种硬币中选取面值恰好是j的硬币个数的最小值
即 \(f[i][j] = min{f[i - 1, j], f[i - 1, j - c_i] + 1, f[i - 1, j - 2c_i] + 2, .... f[i - 1, j - k*c_i] + k}, 其中k*c_i 要小于j, 最大为amount\)
因为要求最小值，所以初始化的时候要求要把每个 \(f[i][j]\) 初始化一个最大值，这里初始化为amount + 1即可，因为体积的最大值就是amount
示例一推导：
f[0] = 0; amount = 11
其他的f[j]为12
coins = [1, 2, 5]
i = 0; i <= 2;
j = coins[i] = coins[0] == 1; j <= amount == 11;
f[j] = min{f[j], f[j - coins[i]] + 1}
=> f[1] = min{f[1], f[1 - 1] + 1} = min{12, 1} = 1
=> f[2] = 2;
=> f[3] = 3;
=> f[4] = 4;
=> f[5] = 5;
=> f[6] = 6;
=> f[7] = 7;
=> f[8] = 8;
=> f[9] = 9;
=> f[10] = 10;
=> f[11] = 11;
i = 1;
j = coins[1] = 2; j <= 11;
f[j] = min{f[j], f[j - coins[i]] + 1}
=> f[2] = min{f[2], f[2 - 2] + 1} = 1;
=> f[3] = min{f[3], f[3 - 2] + 1} = 2;
=> f[4] = min{f[4], f[4 - 2] + 1} = 2;
=> f[5] = min{f[5], f[5 - 2] + 1} = 3;
=> f[6] = min{f[6], f[6 - 2] + 1} = 3;
=> f[7] = min{f[7], f[7 - 2] + 1} = 4;
=> f[8] = min{f[8], f[8 - 2] + 1} = 4;
=> f[9] = 5;
=> f[10] = 5;
=> f[11] = 6;
i = 2;
j = coins[2] = 5; j <= 11;
f[j] = min{f[j], f[j - coins[i]] + 1}
=> f[5] = min{f[5], f[0] + 1} = 1; //之前的不用考虑，因为至少需要背包容量为5才行
=> f[6] = 2;
=> f[7] = 2;
=> f[8] = 3;
=> f[9] = 3;
=> f[10] = 2;
=> f[11] = 3;
f[11] = 3;
代码：
class Solution {
public:
int coinChange(vector& coins, int amount) {
int Max = amount + 1; //初始化一个Max
vector f(amount + 1, Max); //所有的值都初始化为Max
f[0] = 0; // 体积为0的时候一个硬币也无法选择
for (int i = 0; i < coins.size(); ++i) //枚举每一种硬币
// 这里一定是从小到大的，因为我们的递推公式是f[i][j - ci]用的是当前的i
// 如果从大到小，用的就是f[i - 1][j - ci]了
for (int j = coins[i]; j <= amount; ++j) //这里j从coins[i]开始，因为小于的话j - coins[i] 就为负值了
f[j] = min(f[j], f[j - coins[i]] + 1); // 优化版本的递推公式
return f[amount] > amount ? -1 : f[amount]; // 如果f[amount] > Max说明没有兑换成功
}
};
LeetCode 518. 零钱兑换||
给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
假设每一种面额的硬币有无限个。
题目数据保证结果符合 32 位带符号整数。
示例 1：
输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
示例 2：
输入：amount = 3, coins = [2]
输出：0
解释：只用面额 2 的硬币不能凑成总金额 3 。
示例 3：
输入：amount = 10, coins = [10]
输出：1
提示：
1 <= coins.length <= 300
1 <= coins[i] <= 5000
coins 中的所有值 互不相同
0 <= amount <= 5000
思路：
状态划分： \(f[i, j]\) 表示 从\(i\) 种硬币种选取总面值为 \(j\) 得所有方案得集合
属性值：这些方案相加
状态计算：如果方案可行，就是1，否则就是0
根据第 \(i\) 件物品选取件数，\(f[i, j]\) 可分为 $f[i-1, j], f[i - 1, j - c_i], f[i - 1, j - 2c_i], ... , f[i -1, j - kc_i] $
这些方案如果可行就是 \(1\)，不可行就是 \(0\)，然后相加，就是 \(f[i, j]\) 得属性值
其中 \(f[i, 0] = 1\); 因为面值为 \(0\) 只有一种选择，就是什么都不选这一种选择; 然后其余得方案均初始化为 \(0\) ；
优化过后得状态转移方程为: \(f[i, j] = f[i -1, j] + f[i][j - c_i]\)
代码
class Solution {
public:
int change(int amount, vector& coins) {
// 从前i个硬币中选取硬币面值为j得数量
// f[i][j] = f[i - 1][j] + f[i][j - coins[i]]
// f[i, j] = Σ(f[i - 1, j] + f[i - 1, j - ci] + f[i - 1, j - 2ci] ... + f[i-1, j - k*ci])
// 只要满足就是1，否则就是0，然后相加即可
// f[i, 0] = 1; 因为当面值为0时，只有一种选择，就是什么都不选
vector f(amount + 1); //初始化为0
f[0] = 1; //f[0] = 1
for (int i = 0; i < coins.size(); ++i) {
for (int j = coins[i]; j <= amount; j++) {
f[j] = f[j] + f[j - coins[i]]; //状态转移
}
}
return f[amount]; //最终答案f[coins.size()][amount]
}
};
AcWing 4.多重背包问题
有 \(N\) 种物品和一个容量是 \(V\) 的背包。
第 \(i\) 种物品最多有 \(s_i\) 件，每件体积是 \(v_i\)，价值是 \(w_i\)。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。
输入格式
第一行两个整数，\(N，V\)，用空格隔开，分别表示物品种数和背包容积。
接下来有 \(N\) 行，每行三个整数 \(v_i,w_i,s_i\)，用空格隔开，分别表示第 \(i\) 种物品的体积、价值和数量。
输出格式
输出一个整数，表示最大价值。
数据范围
\(0
输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2
输出样例：
10
朴素版Code：（与完全背包朴素版类似）
#pragma once
#include
#include
const int N = 110;
int num, knapsack_volume;
int volume[N], worth[N], sum[N];
int f[N][N], f2[N];
void plain_version()
{
std::cin >> num >> knapsack_volume;
for (int i = 1; i <= num; ++i)
std::cin >> volume[i] >> worth[i] >> sum[i];
for (int i = 1; i <= num; ++i)
for (int j = volume[i]; j <= knapsack_volume; ++j) //这行代码更好，但是分组背包只能用下一行
// for (int j = 0; j <= knapsack_volume; ++j)
for (int k = 0; k <= sum[i] && k * volume[i] <= j; ++k)
f[i][j] = std::max(f[i][j], f[i-1][j - k*volume[i]] + k*worth[i]);
std::cout << f[num][knapsack_volume] << std::endl;
}
当数据范围为
\(0 < N≤1000; 0 < V≤2000; 0
优化版Code：
当数据范围很大时，上述代码就会超时，这里采用多重背包的二进制优化方法.
将s[i]个物品打包成1、2、4、……、2k、C个新物品（C < 2k+1, 这些新物品数量之和等于s[i]），这样0~s[i]内的所有数量都可以用其中的几个新物品只选一次的数量之和代替，这是因为所有数都可以由二进制表示。这样问题转化成对于新物品的01背包问题。
#pragma once
#include
#include
const int N = 110;
int num, knapsack_volume;
int volume[N], worth[N], sum[N];
int f[N][N], f2[N];
void optimize_version()
{
std::cin >> num >> knapsack_volume;
int cnt = 0; //用于分隔所有i的变量
for (int i = 1; i <= num; ++i)
{
int vi, wi, si;
std::cin >> vi >> wi >> si; //输入每组数
//开始分隔成打包的背包
int k = 1; //代表二的零次方
while (k <= si)
{
cnt++; //从1开始
// 开始打包
volume[cnt] = vi * k;
worth[cnt] = wi * k;
si -= k; //减去已经打包好的物品
k *= 2; //乘以二，开始打包下一组
}
// 处理打包后剩余的部分C
if (si > 0)
{
cnt++; // 把剩余的部分打包
volume[cnt] = vi * si;
worth[cnt] = wi * si;
}
}
// 对于所有的cnt件物品进行零一背包处理即可
// 这里不作二维到一维优化的解释了,直接采用一维解决
for (int i = 1; i <= cnt; ++i)
for (int j = knapsack_volume; j >= volume[i]; j--)
f2[j] = std::max(f2[j], f2[j - volume[i]] + worth[i]);
std::cout << f2[knapsack_volume] << std::endl;
}
AcWing 9. 分组背包问题
有 \(N\) 组物品和一个容量是 \(V\) 的背包。
每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 \(v_{ij}\)，价值是 \(w_{ij}\)，其中 \(i\) 是组号，\(j\) 是组内编号
求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。 输出最大价值。
输入格式
第一行有两个整数 \(N，V\)，用空格隔开，分别表示物品组数和背包容量。
接下来有 N 组数据：
每组数据第一行有一个整数 \(S_i\)，表示第 \(i\) 个物品组的物品数量；
每组数据接下来有 \(S_i\) 行，每行有两个整数 \(v_{ij},w_{ij}\)，用空格隔开，分别表示第 \(i\) 个物品组的第 \(j\) 个物品的体积和价值；
输出格式
输出一个整数，表示最大价值。
数据范围
\(0
输入样例
3 5
2
1 2
2 4
1
3 4
1
4 5
输出样例：
8
Code:
#pragma once
#include
const int N = 110;
int num, knapsack_volume;
int volume[N][N], worth[N][N], s[N];
int f[N];
void olny_version()
{
std::cin >> num >> knapsack_volume;
for (int i = 1; i <= num; ++i)
{
std::cin >> s[i];
for (int j = 0; j < s[i]; ++j)
std::cin >> volume[i][j] >> worth[i][j];
}
for (int i = 1; i <= num; ++i)
// 注意从大到小
for (int j = knapsack_volume; j >= 0; --j) //只能是j >= 0, 因为每一组有k件物品，不能逐一枚举
for (int k = 0; k < s[i]; ++k)
if (j >= volume[i][k])
f[j] = std::max(f[j], f[j - volume[i][k]] + worth[i][k]);
std::cout << f[knapsack_volume] << std::endl;
}