网站建设目的要求,南阳公司注册,软件推广怎么做,做网站包括备案吗46. 携带研究材料#xff08;第六期模拟笔试#xff09; 题目描述 小明是一位科学家#xff0c;他需要参加一场重要的国际科学大会#xff0c;以展示自己的最新研究成果。他需要带一些研究材料#xff0c;但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实…46. 携带研究材料第六期模拟笔试 题目描述 小明是一位科学家他需要参加一场重要的国际科学大会以展示自己的最新研究成果。他需要带一些研究材料但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等它们各自占据不同的空间并且具有不同的价值。
小明的行李空间为 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
思路纯正的01背包问题 二维数组方法dp[i][j]中i表示第几个物品j表示容量[0, n]当背包容量大于当前物品权重时递推公式为: dp[i][j]max(dp[i-1][j],dp[i-1][j-weight[i]]value[i])即从左上方推出 容量小于当前物品权重时直接从上方赋值即dp[i][j] dp[i-1][j]。初始化时第一列表示容量为0的最大价值初始化为0第一行中如果当前容量大于等于第1个物品的权重value[0]时初始化为value[0]否则为value[1]。 这样就可以从左上方来推啦。
#includeiostream
#includevector
#include bits/stdc.h
using namespace std;
int solve(int M, int N) {vectorint weight(M,0);vectorint value(M,0);for (int i 0; iM; i) {cinweight[i];}for (int i 0; iM; i) {cinvalue[i];}vectorvectorint dp(M, vectorint(N1, 0));for (int j weight[0]; jN; j) {dp[0][j] value[0];}for (int i 1; iM; i) {for (int j 0; jN; 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]);}}coutdp[M-1][N];
}
int main() {int M,N;while(cinMN){solve(M,N);}return 0;
}一维dp思路二维数组压缩成一维数组即滚动数组可以节省空间。因为观察递推公式dp[i][j]max(dp[i-1][j],dp[i-1][j-weight[i]]value[i])可以看到本行的递推所需数据均在上一行且均在左侧因此可以把上一行的数据复制到本行接着使用。因此定义一个dp[n1]的数组即可保存完毕。dp[j]表示容量为j的最大价值递推公式类似二维 dp[j] max(dp[j], dp[j-weight[i]]value[i])。可以看到如果其实本质思想还是二维数组但是巧妙地运用方法使二维数组变为一维数组节省空间代码简洁。注意遍历顺序在二维数组中可以先物品在容量亦可以反过来但是一维由于压缩只可以先物品后容量容量遍历顺序必须从后向前否则会造成数据覆盖某些物品权重多加。
// 一维dp数组实现
#include iostream
#include vector
using namespace std;int main() {// 读取 M 和 Nint M, N;cin M N;vectorint costs(M);vectorint values(M);for (int i 0; i M; i) {cin costs[i];}for (int j 0; j M; j) {cin values[j];}// 创建一个动态规划数组dp初始值为0vectorint 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. 分割等和子集 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。
示例 1
输入nums [1,5,11,5] 输出true 解释数组可以分割成 [1, 5, 5] 和 [11] 。 示例 2
输入nums [1,2,3,5] 输出false 解释数组不能分割成两个元素和相等的子集。
提示
1 nums.length 200 1 nums[i] 100 思路这个题就是寻找两个集合使其子集的和相等即各为数组总和的一半。如果使用回溯就会是指数级的时间复杂度因此需要用背包问题来看待。物品价值和权重的值相等总容量为target sum/2。递推公式为 dp[j] max(dp[j], dp[j-nums[i]] nums[i])其余循环遍历顺序等和简单01背包相同。最后只需要返回是否可以满足条件就是判断dp[target] target的bool值。
class Solution {
public:bool canPartition(vectorint nums) {int sum 0;// 计算数组总价值量for (auto num : nums) {sum num;}// 如果价值量为奇数不可以平均分成两份因此必为falseif (sum % 2 1) return false;int target sum / 2;// 初始化dp数组为全0vectorint dp(target 1, 0);// 虽然是一维数组做dp但是还是要两层循环外层表示物品个数内层表示容量for (int i 0; inums.size(); i) {for (int j target; j nums[i]; j--) {// 物品的价值和权重时一样的。均为1dp[j] max(dp[j], dp[j-nums[i]]nums[i]);}}// 如果容量等于dp最后得到的状态值返回真if (target dp[target]) {return true;}else {return false;}}
};
