网站推广业务,购物网站管理系统,wordpress nginx版本,电子政务门户网站建设代码一.01背包
46. 携带研究材料#xff08;第六期模拟笔试#xff09; (kamacoder.com)
代码随想录 (programmercarl.com)
携带研究材料:
时间限制#xff1a;5.000S 空间限制#xff1a;128MB
题目描述:
小明是一位科学家#xff0c;他需要参加一场重要的国际科学大会…一.01背包
46. 携带研究材料第六期模拟笔试 (kamacoder.com)
代码随想录 (programmercarl.com)
携带研究材料:
时间限制5.000S 空间限制128MB
题目描述:
小明是一位科学家他需要参加一场重要的国际科学大会以展示自己的最新研究成果。他需要带一些研究材料但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等它们各自占据不同的空间并且具有不同的价值。
小明的行李空间为 N问小明应该如何抉择才能携带最大价值的研究材料每种研究材料只能选择一次并且只有选与不选两种选择不能进行切割。
输入描述:
第一行包含两个正整数第一个整数 M 代表研究材料的种类第二个正整数 N代表小明的行李空间。
第二行包含 M 个正整数代表每种研究材料的所占空间。
第三行包含 M 个正整数代表每种研究材料的价值。
输出描述:
输出一个整数代表小明能够携带的研究材料的最大价值。
输入示例:
6 1
2 2 3 1 5 2
2 3 1 5 4 3 1.dp状态描述
dp[i][j]表示前i个物品中行李空间为j时能带的最大价值
space[i]表示i物品所需空间
value[i]表示i物品的价值
2.递推公式
先遍历物品再遍历背包空间时 新来一个物品i时面对两种情况 带或不带带的前提是当前空间新物品空间I if(jspace[i]) dp[i][j]max(dp[i-1][j-space[i]]value[i],dp[i-1][j]); else dp[i][j]dp[i-1][j]
3. 初始状态
是从一个一个物品开始遍历初始状态有第一个物品即可第一行 for(int i0;in;i) { if(ispace[0]) dp[0][i]value[0]; }
4.遍历顺序 先遍历物品或背包都可以但遍历物品更好理解
#include iostream
#include vector
using namespace std;
int main() {int m 0, n 0;cin m n;vectorint space,value;int tempMm;while(tempM--){int tempSpace;cintempSpace;space.push_back(tempSpace);}tempMm;while(tempM--){int tempValue;cintempValue;value.push_back(tempValue);}// for(auto e : space) coute;// for(auto e : value) coute;//每一个带可能带或不带前面的选择会影响后面//dp[i][j]表示前i个物品中行李空间为j时能带的最大价值 //新来一个物品i时面对两种情况 带或不带//if(jspace[i]) dp[i][j]max(dp[i-1][j-space[i]]value[i],dp[i-1][j]);//else dp[i][j]dp[i-1][j]vectorvectorint dp(m,vectorint(n1,0));// //初始状态第一行即可for(int i0;in;i){if(ispace[0]) dp[0][i]value[0];}for(int i1;im;i){for(int j1;jn;j){if(jspace[i]) dp[i][j]max(dp[i-1][j-space[i]]value[i],dp[i-1][j]);else dp[i][j]dp[i-1][j];}}coutdp[m-1][n];return 0;
} 二.完全背包
52. 携带研究材料第七期模拟笔试 (kamacoder.com)
代码随想录 (programmercarl.com)
52. 携带研究材料第七期模拟笔试
时间限制1.000S 空间限制128MB
题目描述:
小明是一位科学家他需要参加一场重要的国际科学大会以展示自己的最新研究成果。他需要带一些研究材料但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等它们各自占据不同的重量并且具有不同的价值。
小明的行李箱所能承担的总重量为 N问小明应该如何抉择才能携带最大价值的研究材料每种研究材料可以选择无数次并且可以重复选择。
输入描述:
第一行包含两个整数NV分别表示研究材料的种类和行李空间
接下来包含 N 行每行两个整数 wi 和 vi代表第 i 种研究材料的重量和价值
输出描述:
输出一个整数表示最大价值。
输入示例:
4 5
1 2
2 4
3 4
4 5
输出示例:
10 1.dp状态描述(与01背包相同)
dp[i][j]表示前i个物品中行李空间为j时能带的最大价值
space[i]表示i物品所需空间
value[i]表示i物品的价值
2.递推公式
先遍历物品再遍历背包空间时 新来一个物品i时面对两种情况 带或不带带的前提是当前空间新物品空间I带的话可以选择带n个则带的结果是以dp[i][j-space[i]]value[i]表示因为此时只需要空间变小即可依旧可以选择到第i个物品 if(jspace[i]) dp[i][j]max(dp[i][j-space[i]]value[i],dp[i-1][j]); else dp[i][j]dp[i-1][j]
3. 初始状态
是从一个一个物品开始遍历初始状态有第一个物品即可第一行也有01背包略有不同 for(int i0;in;i) { if(ispace[0]) dp[0][i]max(dp[0][i-space[0]]value[0],value[0]); }
#include iostream
#include vector
using namespace std;
int main() {int m 0, n 0;cin m n;vectorint space,value;int tempMm;while(tempM--){int tempSpace,tempValue;cintempSpacetempValue;space.push_back(tempSpace);value.push_back(tempValue);}vectorvectorint dp(m,vectorint(n1,0));// //初始状态第一行即可for(int i0;in;i){if(ispace[0]) dp[0][i]max(dp[0][i-space[0]]value[0],value[0]);}for(int i1;im;i){for(int j1;jn;j){//与01背包唯一不同点就是选择带之后依然可以选择继续带则用dp[i][j-space[i]]value[i]if(jspace[i]) dp[i][j]max(dp[i][j-space[i]]value[i],dp[i-1][j]);else dp[i][j]dp[i-1][j];}}coutdp[m-1][n];return 0;
}
三.一维数组解题
上述代码中都是按“一行”结束后进行下一行的值计算且每次计算最多只间隔一行没有出现间隔多行的情况在计算第100行时只需要第99行那么保存的0-98行都是浪费内存。
3.1 01背包
1.状态描述
dp[j]表示空间为j时能装下的最大重量
2.递推公式
if(jspace[i]) dp[j]max(dp[j-space[i]]value[i],dp[j]);
3.初始状态 for(int i0;in;i) { if(ispace[0]) dp[i]value[0]; }
4.遍历顺序
如果是正序遍历物品i时
假设dp[j]已经装入了物品i而后的dp[jn]也可能装入物品i可能dp[j-space[i]]的值已经变化了 不再是未装入物品i时的值
举一个例子物品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]装入了两次物品0
如果是倒序则不会出现重复装入情况因为dp[j-space[i]]未变化未装入物品i
#include iostream
#include vector
using namespace std;
int main() {int m 0, n 0;cin m n;vectorint space,value;int tempMm;while(tempM--){int tempSpace;cintempSpace;space.push_back(tempSpace);}tempMm;while(tempM--){int tempValue;cintempValue;value.push_back(tempValue);}vectorint dp(n1,0);// //初始状态第一行即可for(int i0;in;i){if(ispace[0]) dp[i]value[0];}for(int i1;im;i){for(int jn;jspace[i];j--){dp[j]max(dp[j-space[i]]value[i],dp[j]);}}coutdp[n];return 0;
} 3.2 完全背包
52. 携带研究材料第七期模拟笔试 (kamacoder.com)
题目与01背包唯一不同点是物品i可以带入多个
1.将01背包的遍历顺序改为正序
2.修改初始状态 dp[i]max(dp[i-space[0]]value[0],value[0]);
#include iostream
#include vector
using namespace std;
int main() {int m 0, n 0;cin m n;vectorint space,value;int tempMm;while(tempM--){int tempSpace,tempValue;cintempSpacetempValue;space.push_back(tempSpace);value.push_back(tempValue);}vectorint dp(n1,0);for(int ispace[0];in;i){dp[i]max(dp[i-space[0]]value[0],value[0]);}for(int i1;im;i){for(int jspace[i];jn;j){dp[j]max(dp[j-space[i]]value[i],dp[j]);}}coutdp[n];return 0;
}
