微信url短网址在线生成_品牌建设与电商发展的关系_邯郸seo优化公司_下载应用商店

第九章 动态规划 part03

正式开始背包问题。背包问题还是挺难的，虽然大家可能看了很多背包问题模板代码，感觉挺简单，但其实大部分对其理解并不够深入。

• 如果从未听说过背包问题，可以先看文字讲解，慢慢了解这是干什么的。
• 如果做过背包类问题，可以先看视频，很多内容可能是自己平时没有考虑到位的。

背包问题在力扣上没有原题，大家可以先了解理论，今天就安排一道具体的题目。

---

详细布置

01 背包问题（二维）

文字讲解：点击查看
视频讲解：点击查看

这题还是建议看视频，看讲解看的人头疼，最重要的是把这张图看明白，很明显，这张图就是在只考虑前几个物品的情况下，背包重量的情况下，最大价值多少。
注意递推公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);就是看dp[i - 1][j]，相当于背包含量没有+1之前能拿最大价值，dp[i - 1][j - weight[i]] + value[i]，是去掉当前物品重量最大价值，dp[i - 1][j - weight[i]] 再加上当前物品价值value[i]，取最大值。
把这两个核心看懂，这题就很好解决了。

#include <bits/stdc++.h>//使用 #include <bits/stdc++.h> 是一种在比赛或快速编程时常用的做法，它会引入 C++ 标准库的所有头文件。虽然它方便，但在实际开发中不建议使用，因为这样会增加编译时间，并且不符合标准。
using namespace std;int main() {int n, bagweight;// bagweight代表行李箱空间cin >> n >> bagweight;vector<int> weight(n, 0); // 存储每件物品所占空间vector<int> value(n, 0);  // 存储每件物品价值for(int i = 0; i < n; ++i) {cin >> weight[i];}for(int j = 0; j < n; ++j) {cin >> value[j];}vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));for (int j = weight[0]; j <= bagweight; j++) {dp[0][j] = value[0];}//初始化重量数组for(int i = 1; i < weight.size(); i++) { // 遍历物品价值for(int j = 0; j <= bagweight; j++) { // 遍历背包容量if (j < weight[i]) dp[i][j] = dp[i - 1][j]; else {dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);}}}cout << dp[n - 1][bagweight] << endl;return 0;
}

01 背包问题（一维）

文字讲解：点击查看
视频讲解：点击查看
核心是：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
其实可以发现如果把dp[i - 1]那一层拷贝到dp[i]上，表达式完全可以是：dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]);顿时感觉豁然开朗，直接复制粘贴。不想写了。确实挺不错的思路。对于这类题目，更新前一个就相当于更新自身。

// 一维dp数组实现
#include <iostream>
#include <vector>
using namespace std;int main() {// 读取 M 和 Nint M, N;cin >> M >> N;vector<int> costs(M);vector<int> values(M);for (int i = 0; i < M; i++) {cin >> costs[i];}for (int j = 0; j < M; j++) {cin >> values[j];}// 创建一个动态规划数组dp，初始值为0vector<int> dp(N + 1, 0);// 外层循环遍历每个类型的研究材料for (int i = 0; i < M; ++i) {// 内层循环从 N 空间逐渐减少到当前研究材料所占空间for (int j = N; j >= costs[i]; --j) {// 考虑当前研究材料选择和不选择的情况，选择最大值dp[j] = max(dp[j], dp[j - costs[i]] + values[i]);}}// 输出dp[N]，即在给定 N 行李空间可以携带的研究材料最大价值cout << dp[N] << endl;return 0;
}

416. 分割等和子集

本题是 01 背包的应用类题目。
计算总和：首先计算数组元素的总和。如果总和是奇数，则不能分割成两个相等的子集，直接返回 false。

目标值：如果总和是偶数，目标值就是总和的一半，即 target = sum / 2。只要找到能把这个背包装满的sum值即可。相当于一个个判断：背包大小1能装的最大值，背包大小2能装的最大值，背包大小3能装的最大值，一直到目标背包大小target能装的最大值是否为target，是说明可以。

动态规划：使用动态规划来检查是否存在一个子集，其和等于 target。我们可以使用一个int数组 dp，其中 dp[j] 表示是否存在一个子集的和为 j。

状态转移：对于每个元素 num，从 target 开始向下更新 dp 数组。如果当前的 j 可以通过添加 num 来实现，,dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);。

文字讲解：点击查看
视频讲解：点击查看

class Solution {
public:bool canPartition(vector<int>& nums) {int sum = std::accumulate(nums.begin(), nums.end(), 0);// 如果总和是奇数，无法分割if (sum % 2 != 0) return false;int target = sum / 2;std::vector<int> dp(target + 1, 0);dp[0] = 0; // 0 可以总是被表示for (int num : nums) {for (int j = target; j >= num; --j) {dp[j]=max(dp[j],dp[j-num]+num);}}if(dp[target]==target)return 1;return 0;}
};

---

代码还是比较好写的。研究生太忙了，太久没学习了，天天摸鱼摆烂，假期又出去玩。一旦落下的太多，越来越想开摆。一点也不想学。卡尔的卡码网用起来很不习惯，不想跟着用，还是刷完动态规划即可。把自己买的书刷完就行。为自己而学。一点点忙起来也好。