题目描述
小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。他需要带一些研究材料，但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等，它们各自占据不同的空间，并且具有不同的价值。
小明的行李空间为 N，问小明应该如何抉择，才能携带最大价值的研究材料，每种研究材料只能选择一次，并且只有选与不选两种选择，不能进行切割。
输入描述
第一行包含两个正整数，第一个整数 M 代表研究材料的种类，第二个正整数 N，代表小明的行李空间。
第二行包含 M 个正整数，代表每种研究材料的所占空间。
第三行包含 M 个正整数，代表每种研究材料的价值。
输出描述
输入示例
6 1
2 2 3 1 5 2
2 3 1 5 4 3输出示例
5思路：
1.dp[i][j]是能够携带的研究材料的最大价值。i是材料种类，j是行李空间。
2.dp[i][j] = max(dp[i – 1][j], dp[i – 1][j – weight[i]] + value[i]);
3.初始化：
首先从dp[i][j]的定义出发，如果背包容量j为0的话，即dp[i][0]，无论是选取哪些物品，背包价值总和一定为0。
当 j < weight[0]的时候，dp[0][j] 应该是 0，因为背包容量比编号0的物品重量还小。
当j >= weight[0]时，dp[0][j] 应该是value[0]，因为背包容量放足够放编号0物品。
4.先遍历 物品还是先遍历背包重量呢？其实都可以， 但是先遍历物品更好理解。
代码如下：
#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];
}
// dp数组, dp[i][j]代表行李箱空间为j的情况下,从下标为[0,i]的物品里面任意取,能达到的最大价值
vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));
// 初始化, 因为需要用到dp[i - 1]的值
// j < weight[0]已在上方被初始化为0
// j >= weight[0]的值就初始化为value[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]; // 如果装不下这个物品,那么就继承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;
}
另外，可以发现，在递推公式dp[i][j] = max(dp[i – 1][j], dp[i – 1][j – weight[i]] + value[i])中，单看i可知两个情况都是dp[i-1]拷贝到dp[i]。
所以可以让所有都往后一位，这样就可以省略掉i，用一维数组即可。
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);但二维dp遍历的时候，背包容量是从小到大，而一维dp遍历的时候，背包是从大到小。
为什么呢？
倒序遍历是为了保证物品i只被放入一次！。但如果一旦正序遍历了，那么物品0就会被重复加入多次！
举一个例子：物品0的重量weight[0] = 1，价值value[0] = 15
如果正序遍历
dp[1] = dp[1 – weight[0]] + value[0] = 15
dp[2] = dp[2 – weight[0]] + value[0] = 30
此时dp[2]就已经是30了，意味着物品0，被放入了两次，所以不能正序遍历。
为什么倒序遍历，就可以保证物品只放入一次呢？
倒序就是先算dp[2]
dp[2] = dp[2 – weight[0]] + value[0] = 15 （dp数组已经都初始化为0，即dp[1]=0）
dp[1] = dp[1 – weight[0]] + value[0] = 15、
代码如下：
// 一维dp数组实现
#include <iostream>
#include <vector>
using namespace std;
int main() {
// 读取 M 和 N
int 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，初始值为0
vector<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;
}
背包的体积为sum / 2
背包要放入的商品（集合里的元素）重量为 元素的数值，价值也为元素的数值
背包如果正好装满，说明找到了总和为 sum / 2 的子集。
递推公式：dp[j] = max(dp[j], dp[j – weight[i]] + value[i]);
代码如下：
class Solution {
public:
bool canPartition(vector<int>& nums) {
//01背包，容量是sum/2;
int sum=0;
for(int x:nums){
sum+=x;
}
if (sum % 2 == 1) return false;
vector<int> dp(10001,0);
for(int i=0;i<nums.size();i++){
for(int j=sum/2;j>=nums[i];j--){
dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
}
}
if(dp[sum/2]==sum/2) return true;
return false;
}
};
有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
- 如果
x == y，那么两块石头都会被完全粉碎； - 如果
x != y，那么重量为x的石头将会完全粉碎，而重量为y的石头新重量为y-x。
最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。
示例 1：
输入：stones = [2,7,4,1,8,1] 输出：1 解释： 组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]， 组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]， 组合 2 和 1，得到 1，所以数组转化为 [1,1,1]， 组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。
示例 2：
输入：stones = [31,26,33,21,40] 输出：5
思路：
本题其实就是尽量让石头分成重量相同的两堆，相撞之后剩下的石头最小，这样就化解成01背包问题了。
代码如下：
class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
int sum = 0;
for (int x : stones) {
sum += x;
}
int target = sum / 2;
vector<int> dp(1501, 0); // 30*100/2+1
for (int i = 0; i < stones.size(); i++) {
for (int j = target; j >= stones[i]; j--) {
dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
}
}
return sum - dp[target] * 2;
}
};
给你一个非负整数数组 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
思路：
先想办法转化成背包问题：用nums装满容量为x的背包，有几种方法。
假设加法的总和为x，那么减法对应的总和就是sum – x。
所以我们要求的是 x – (sum – x) = target
x = (target + sum) / 2
1.定义dp数组：dp[j]，表示：填满j（包括j）这么大容积的包，有dp[j]种方法。
2.dp[j]=dp[j]+dp[j-nums[i]]
3.初始化：d[0]=1
4.确定遍历顺序：遍历物品放在外循环，遍历背包在内循环，且内循环倒序
代码如下：
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int sum = 0;
for (int i = 0; i < nums.size(); i++)
sum += nums[i];
if (abs(target) > sum)
return 0; // 此时没有方案
if ((target + sum) % 2 == 1)
return 0; // 此时没有方案
int bagSize = (target + sum) / 2;
vector<int> dp(bagSize + 1, 0);
dp[0] = 1;
for (int i = 0; i < nums.size(); i++) {
for (int j = bagSize; j >= nums[i]; j--) {
dp[j] += dp[j - nums[i]];
}
}
return dp[bagSize];
}
};
暂无评论