动态规划-背包01问题推理与实践
背包01问题描述:
有storage大小的背包和weights.size()数量的物品,每个物品i对应的物品大小为sizes[i],价值为values[i],在不超过storage大小的情况下,如何装载物品使背包中的values和最大.
物品大小: vector<int> sizes;
物品价值: vector<int> values;
背包容量: <int> storage;
理解(状态转移公式的推理):
构建二维数组dp[i][j],定义式为 std::vector<std::vector<int>> dp(sizes.size(),std::vector<int>(storage + 1,0));默认值为0;
dp[i][j] 的意义是在前 i 个物品中选择任意少于等于 i 个物品,其总大小不超过 j 的最大价值和.
则同理 dp[i - 1][j] 为在前 i - 1 物品中选择任意少于等于 i - 1 个物品,其总大小不超过 j - 1的最大价值和,此即为子状态.
假设求取dp[i][j],则考虑两种情况:
①第i个物品取的可能
②第i个物品不取的可能
针对上述情况进行分类讨论:
①已知dp[i-1][j],此时背包已满,则应腾出某物品以装在第 i 物品,则装载前必须知道dp[i - 1][j - sizes[i]]的值,即背包扣除第i个物品的大小后的最大价值装载方式[1],则可推导出dp[i][j] = dp[i - 1][j - sizes[i]] + values[i];
②已知dp[i - 1][j],此时第 i 个物品的价值过低或大小过大,不适合替换背包中的物品,则推理出dp[i][j] = dp[i - 1][j];
因为无法知道上述两种情况何时会发生,应该取两者的较大值:
dp[i][j] = std::max(dp[i - 1][j - sizes[i]] + values[i],dp[i - 1][j]);
此即为背包01问题的状态转移公式.
代码实现dp数组如下[2]:
//初始化第一个物品放入背包的子状态,即dp[0][j],此处的j代表的是>=第一个物品的大小的位置处,都填充values[0],注意子数组的额存放索引为增长的storage.
for(int j = sizes[0]; j <= storage; j++) {
dp[0][j] = values[0];
}
//构建dp数组
for(int i = 1; i < sizes.size(); i++) {
for(int j = 0; j <= storage; j++) {
//该装载的物品过大,即使只装它一个也装不下,直接返回不装载的情况即可
if(j < sizes[i]) dp[i][j] = dp[i - 1][j];
else dp[i][j] = std::max(
dp[i - 1][j - sizes[i]] + values[i],
dp[i - 1][j]
);
}
}
完整代码(对应2. 01背包问题 - AcWing题库):
#include <iostream>
#include <vector>
#include <algorithm>
int main(int argc,char** argv) {
std::vector<int> sizes;
std::vector<int> values;
int storage;
int size;
std::cin >> size >> storage;
for(int i = 0; i < size; i++) {
int t_size;
int t_value;
std::cin >> t_size >> t_value;
sizes.push_back(t_size);
values.push_back(t_value);
}
std::vector<std::vector<int>> dp(sizes.size(),std::vector<int>(storage + 1,0));
for(int j = sizes[0]; j <= storage; j++) {
dp[0][j] = values[0];
}
for(int i = 1; i < sizes.size(); i++) {
for(int j = 0; j <= storage; j++) {
if(j < sizes[i]) dp[i][j] = dp[i - 1][j];
else dp[i][j] = std::max(
dp[i - 1][j - sizes[i]] + values[i],
dp[i - 1][j]
);
}
}
//Debug查看部分
// for(int i = 0; i < size; i++) {
// for(int j = 0; j <= storage; j++) {
// std::cout << "[" << i << "]" << "[" << j << "]" << " = " << dp[i][j] << std::endl;
// }
// }
std::cout << dp[size - 1][storage];
return 0;
}
一维数组简化理解:
构建dp[j]一维数组,定义式为 std::vector<std::vector<int>> dp(storage + 1,0);
dp[j]数组意义为背包容量为j时,背包的最大价值为dp[j];
一维数组的遍历代码:
for(int i = 0; i < sizes.size(); i++) {
for(int j = storage; j >= sizes[i]; j--) {
dp[j] = std::max(
dp[j - sizes[i]] + values[i],
dp[j]
);
}
}
这里复用dp[j]的推理是,外层循环可以理解为依次遍历当次放入的物品 i 与放入该物品时容量为 j 的最大价值计算,即dp[j]为复用上一层循环 i = i - 1, j = j 时的最大价值,所变化的是考虑了新加入的 i 物品;内层循环反向遍历的理由因此可以推理得出,若正向进行遍历时,外层的i物品会被内层多次放入背包中(多次被遍历到),而反向遍历则不会重复遍历到,即举例以下情况:
// i:(in) 1 2 3...sizes.size() - 1 当 i = 2时
// j:(in) size[i] size[i] + 1 size[i] + 2...storage 当 j = x - 1(实际值在此例中不重要,合理即可)时
dp[j] = dp[j - sizes[i]] + values[i] == dp[x - 1] = dp[x - 1 - sizes[2]] + values[2];
//当 i = 2时
//当 j = x时
dp[j] = dp[j - sizes[i]] + values[i] == dp[x] = dp[x - sizes[2]] + values[2];
//观察可得: 在j:容量增长的情况下重复考虑了 i = 2 的情况,即重复加入了背包
//此时我们反向考虑
//i:(in) 与上文相同, 当i = 2时
//j:(in) storage... size[i] 当 j = x + 1(同上)时
dp[j] == dp[x + 1] = dp[x + 1 - size[2]] + values[2];
//当 i = 2时
//当 j = x时
dp[j] == dp[x] = dp[x - sizes[2]] + values[2];
//观察可得: 在j:容量递减的情况下,dp[x + 1] 依赖于上一次外层循环的dp[x + 1 - sizes[2]]值,而与此次循环的dp[x]值无关,故不会出现重复加入的情况
一维数组的初始化方式:
一维数组dp[j]不需要像二维数组dp[i][j]那样繁琐的初始化
仅仅只需要设置整体默认值(一般为0)即可,可参考定义式[3]
完整代码(对应416. 分割等和子集(LeetCode)):
class Solution {
public:
bool canPartition(std::vector<int>& nums) {
int sum{0};
for(int elem : nums) {
sum += elem;
}
if(sum % 2 != 0) return false;
int target = sum / 2;
std::vector<int> dp(target + 1,0);
for(int i = 0; i < nums.size(); i++) {
for(int j = target; j >= nums[i]; j--) {
dp[j] = std::max(
dp[j],
dp[j - nums[i]] + nums[i]
);
}
}
if(dp[target] == target) return true;
else return false;
}
}
例题理解(对应494. 目标和(LeetCode)):
给你一个非负整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
- 例如，
nums = [2, 1]，可以在2之前添加'+'，在1之前添加'-'，然后串联起来得到表达式"+2-1"。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
示例 1：
输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3
示例 2：
输入：nums = [1], target = 1
输出：1
提示：
1 <= nums.length <= 200 <= nums[i] <= 10000 <= sum(nums[i]) <= 1000-1000 <= target <= 1000
解题思路:
将nums数组的选择抽取划分为题干对应的两种状态,"+" 和 "-";我们称 "+" 的成员集成为left数组,"-" 的成员集成为right数组;
显然可见:
① int sum{0}; for: sum += nums.elems; sum = sum(left) + sum(right); sum => const //对nums数组成员求和,其值为定值,且可转换为left和 right的成员和
② sum(left) - sum(right) = target; target => const //满足题目要求的left和right,其相减值为定值
①和②可推理出
target + sum = sum(left) * 2 => sum(left) = (target + sum) / 2; //依此可得,sum(left)也为定值
推导出,当我们满足sum(left)为 (target + sum) / 2时,便可满足题干要求,抽象为当我们装满容量为sum(left)的背包时,dp[left]所存储的值即为解
确定背包定义式: std::vector<int> dp (storage + 1,0); storage = (sum + target) / 2;
确定背包状态转移公式: dp[j] = dp[j] + dp[j - nums[i]] + nums[i] == dp[j] += dp[j - nums[i]] + nums[i];解释为在背包容量为j时,当前dp[j]的值为装入选择该i物品加入left数组和不加入left数组后的满足次数;
该题目与许多其他背包问题的思维大致相同,都是将题目问题转换为可理解的背包01问题.
完整代码:
class Solution {
public:
int findTargetSumWays(std::vector<int>& nums, int target) {
int sum{0};
for(int elem : nums) {
sum += elem;
}
if((target + sum) % 2 != 0 || abs(target) > sum) return 0;
int storage = (sum + target) / 2;
std::vector<int> dp (storage + 1,0);
dp[0] = 1;
for(int i = 0; i < nums.size(); i++) {
for(int j = storage; j >= nums[i]; j--) {
dp[j] += dp[j - nums[i]];
}
}
return dp[storage];
}
};
文章参考于: 代码随想录,CSDN,CNBlog等各优秀编辑者,开发者的优质文章作品.
--2024.11.10 Neko 总结
这里是在推理在storage为 j - sizes[i] 的情况下的最大价值(dp[i - 1][j - sizes[i]),从而求得装载第i个物品后总sizes <= storage的最大价值,因为dp[i - 1][ j -sizes[i]]为子状态,其已经定义且为已知结果,故能推导出选择第i个物品时的最大价值 ↩︎
这里的dp[i][j] 初始化代码为 (sizes.size(),std::vector<int>(storage + 1,0)); 此处为兼容语言数组特性,将对其自然数字记录方式;第i个物品的大小在sizes[i - 1]处存放,而重量则符合自然数字规律(0-storage) ↩︎
C++的此定义式本身也初始化了所有元素(为0),语法请自行查略 ↩︎