知名营销类网站,京东联盟怎么做网站,仿卢松松博客网站源码,企业网站规范题目#xff08;卡玛网T46#xff09;#xff1a;
小明是一位科学家#xff0c;他需要参加一场重要的国际科学大会#xff0c;以展示自己的最新研究成果。他需要带一些研究材料#xff0c;但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等卡玛网T46
小明是一位科学家他需要参加一场重要的国际科学大会以展示自己的最新研究成果。他需要带一些研究材料但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等它们各自占据不同的空间并且具有不同的价值。
小明的行李空间为 N问小明应该如何抉择才能携带最大价值的研究材料每种研究材料只能选择一次并且只有选与不选两种选择不能进行切割。 方法本题是经典的01背包问题这种问题有固定的思考方式先推导理解一下。同样还是根据动态规划的五步法来思考。
1dp数组的含义因为这里涉及到背包容量和物品的重量两个元素所以需要二维数组dp[i][j]来表示dp数组其含义可以理解为当背包容量为j时任选0-i的物品可以获得的最大价值。
2dp递推公式的推导dp[i][j]的获得方式我们可以从两种地方得到一个是当前不放i物品一个是当前放i物品。当不放i物品时当前的最大价值很容易得到就是有上一层状态得到为dp[i-1][j]如果当前放i物品的话首先要预留足够放置i物品的空间dp[i][j-weight[i]],此时能获得的最大重量即使dp[i][j-weight[i]] value[j]因此这两种情况下可以得到递推公式dp[i][jmax(dp[i-1][j], dp[i][j-weight[i]] value[j])。
3初始化当背包容量为0时没有什么好考虑的肯定价值都为0因每次dp[i][0]0物品0的放置在背包容量小于weight[0]时为0大于等于时为value[0]
4遍历顺序从小到大先物品再背包
5举例推导dp数组
题解
#includebits/stdc.h
using namespace std;
int main(){int n, bagweight;cin n bagweight;vectorint weight(n, 0);vectorint value(n, 0);for(int i 0; i n; i){cin weight[i];}for(int j 0; j n; j){cin value[j];}vectorvectorint dp(weight.size(), vectorint(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]; // 如果装不下这个物品,那么就继承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;
}
