体育器材网站建设方案竞价托管多少钱一个月
动态规划day34|背包理论基础（1）（2）、46.携带研究材料、416. 分割等和子集
- 背包理论基础（1）——二维
- 背包理论基础（2）——一维
- 46.携带研究材料(卡码网 01背包)
- 1. 二维背包
- 2. 一维背包
- 416. 分割等和子集
背包理论基础（1）——二维
-
背包问题的理论基础重中之重是01背包
-
01 背包问题：
- 有n件物品（记为0、1、2…n-1）和一个最大容量为w (记为0、1、2…w)的背包。
- 第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次。
求解：放入哪些物品，可以使得背包内的总价值最大
-
五步分析：
-
确定dp数组以及下标的含义
- dp [i] [j] 中 i 来表示物品、j表示背包容量。
- dp [i] [j] 表示最大的价值总和，而且是从下标为[0-i]的物品里任意取，放进容量为j的背包。
-
确定递推公式
- 物品i放不下：
dp[i][j] = dp[i-1][j]; - 物品i能放下：
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
- 物品i放不下：
-
dp数组如何初始化
-
当j=0时，dp显然为0；当i=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]);}
-
- 举例验证（略）
背包理论基础（2）——一维
-
确定dp数组以及下标的含义
- 在一维dp数组中，**dp[j]**表示：容量为j的背包的最大价值总和
-
确定递推公式
- dp[i]本质就是由上一层 dp[i-1] 拷贝得来
- 递推公式为：
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
-
dp数组如何初始化
- vector dp(bagweight+1，0)；
-
确定遍历顺序
-
只能先遍历物品，后遍历背包。
-
背包必须倒序，目的：保证物品i只被放入一次
-
for(int i = 0; i < weight.size(); i++) // 遍历物品for(int j = bagWeight; j >= weight[i]; j--) // 遍历背包容量dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);当背包正序的时候，dp[j - weight[i]]里面是可能含有物品i的，这是因为每一层的dp都会覆盖前一层，而我们需要的正是前一层的值。所以我们从后面开始，这样前面的值就仍然是上一轮的。
-
注意j >= weight[i]，因为当容量小于第i个物品的重量时，j - weight[i]<0,会触发异常。所以j - weight[i]<0的时候，直接继承上一层的值就可以了，也就是不需要任何操作。而在二维背包中式需要单独考虑的，因为它没有继承。
-
-
举例验证（略）
46.携带研究材料(卡码网 01背包)
题目描述
小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。他需要带一些研究材料，但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等，它们各自占据不同的空间，并且具有不同的价值。
小明的行李空间为 N，问小明应该如何抉择，才能携带最大价值的研究材料，每种研究材料只能选择一次，并且只有选与不选两种选择，不能进行切割。
输入描述
第一行包含两个正整数，第一个整数 M 代表研究材料的种类，第二个正整数 N，代表小明的行李空间。
第二行包含 M 个正整数，代表每种研究材料的所占空间。
第三行包含 M 个正整数，代表每种研究材料的价值。
输出描述
输出一个整数，代表小明能够携带的研究材料的最大价值。
输入示例
6 1
2 2 3 1 5 2
2 3 1 5 4 3
输出示例
5
提示信息
小明能够携带 6 种研究材料，但是行李空间只有 1，而占用空间为 1 的研究材料价值为 5，所以最终答案输出 5。
数据范围：
1 <= N <= 5000
1 <= M <= 5000
研究材料占用空间和价值都小于等于 1000
1. 二维背包
#include <bits/stdc++.h>
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];elsedp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);}cout<<dp[n-1][bagweight]<<endl;return 0;
}
2. 一维背包
#include <bits/stdc++.h>
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<int> dp(bagweight+1,0);for(int i=0;i<weight.size();i++)for(int j=bagweight;j>=weight[i];j--)dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);cout<<dp[bagweight]<<endl;return 0;
}
416. 分割等和子集
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1：
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2：
输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。
提示：
1 <= nums.length <= 2001 <= nums[i] <= 100
class Solution {
public:bool canPartition(vector<int>& nums) {int sum=0;for(int i=0;i<nums.size();i++)sum+=nums[i];if(sum%2==1) return false;int target=sum/2;vector<int> dp(10001,0);for(int i=0;i<nums.size();i++)for(int j=target;j>=nums[i];j--)dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]);return dp[target]==target;}
};
难点：
- 正确识别出该问题是背包问题！（可能需要熟能生巧）而且这是一个特殊的背包问题，每一个物品的质量和价值是相等的，共用这一个数组。
易错点：
- dp数组的个数是由元素总和决定的，而不是元素个数，要注意。