工业设计网站 知乎,做的网站百度搜不到,吴忠北京网站建设,无锡网站制作多少钱动态规划之0-1背包问题 文章目录 动态规划之0-1背包问题一、先给出代码二、讲解第一步#xff1a;初始化第二步#xff1a;动态规划#xff0c;填表第三步#xff1a;回溯#xff0c;找到选择方案总结 三、进阶#xff08;用一维数组解决问题#xff09; 一、先给出代码…动态规划之0-1背包问题 文章目录 动态规划之0-1背包问题一、先给出代码二、讲解第一步初始化第二步动态规划填表第三步回溯找到选择方案总结 三、进阶用一维数组解决问题 一、先给出代码
#include iostream
#include vector
#include algorithm
using namespace std;
void Bp(vectorint weights, vectorint values, vectorvectorint dp,int bag_weight,vectorintresult)
{//初始化for (int j weights[0]; j bag_weight; j) {dp[0][j] values[0];}//动态规划填表//因为第一行是要单独初始化的后面还要建立在第一行的基础上所以i初始值为1for (int i 1; i weights.size(); i) {for (int j 0; j bag_weight; j) {//第一种情况第i个物品就算单独放也不行第二种情况拿上一个没i的结果和有i的比较if (j weights[i]) {dp[i][j] dp[i - 1][j];}else {dp[i][j] max(dp[i - 1][j], dp[i-1][j-weights[i]] values[i]);}}}//统计拿走的东西种类for (int i weights.size() - 1, j bag_weight; i 0; i--) {if (dp[i][j] dp[i - 1][j]) {result.push_back(i);j - weights[i];}if (i 1 dp[i][j] !values[i]) {//如果dp[1][j]的不等于values[1]result.push_back(0);}}
}int main()
{int num,weight, value,bag_weight;vector int weights ;vectorint values ;vectorintresult;cout Please enter the number of weights and values! endl;//输入东西种类数量cin num;//分别输入重量和价值cout Please enter the weights! endl;for (int i 0; i num;i) {cin weight;weights.push_back(weight);}cout Please enter the values! endl;for (int i 0; i num; i) {cin value;values.push_back(value);}cout Please enter the weight of bag! endl;cin bag_weight ;vectorvectorint dp(weights.size() 1, vectorint(bag_weight 1, 0));Bp(weights,values,dp,bag_weight,result);//输出总额和拿走的东西种类cout The total prize is : dp[weights.size() - 1][bag_weight] endl;cout The way of result is : endl;for (auto it result.rbegin(); it ! result.rend();it) {cout *it ;}return 0;
}二、讲解
关于dp数组
**dp[i][j]表示在考虑前i个物品并且背包容量为j的情况下能够获得的最大价值。**这样的一个二维数组可以用来记录不同状态下的最优解其中i表示物品的编号从0开始j表示背包的容量。根据题目的要求我们希望找到dp[weights.size() - 1][bag_weight]即在考虑所有物品且背包容量为bag_weight的情况下能够获得的最大价值。
第一步初始化
for (int j weights[0]; j bag_weight; j) {dp[0][j] values[0];
}在动态规划中我们通常需要构建一个状态转移表格dp数组来记录状态的变化在01背包问题中我们有两个状态背包容量和物品编号。这里的代码初始化了第一行表示只有第一个物品时对于不同背包容量的情况下能够获得的最大价值。这是一个边界条件因为只有一个物品所以它要么放入背包要么不放入所以只有当背包容量大于等于第一个物品的重量时才能将其放入背包获得对应的价值。
第二步动态规划填表
for (int i 1; i weights.size(); i) {for (int j 0; j bag_weight; j) {if (j weights[i]) {dp[i][j] dp[i - 1][j];} else {dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weights[i]] values[i]);}}
}这部分代码构建了整个dp数组。在这里我们逐步考虑每个物品以及在不同背包容量下获得的最大价值。对于每个物品我们有两个选择放入背包或者不放入背包。每个单元格dp[i][j]的值是根据以下两种情况来确定的
如果第i个物品的重量weights[i]大于当前背包容量j那么不能将第i个物品放入背包所以最大价值与上一个状态dp[i-1][j]相同。如果第i个物品的重量weights[i]小于等于当前背包容量j那么我们有两种选择放入第i个物品或者不放入。我们需要比较这两种选择对应的最大价值选择其中较大的值作为dp[i][j]的值。
第三步回溯找到选择方案
for (int i weights.size() - 1, j bag_weight; i 0; i--) {if (dp[i][j] dp[i - 1][j]) {result.push_back(i);j - weights[i];}if (i 1 dp[i][j] ! values[i]) {result.push_back(0);}
}这部分代码用于回溯找出实际选择了哪些物品放入背包从而达到最大价值。从dp数组的右下角即dp[weights.size() - 1][bag_weight]开始我们倒退遍历dp数组。如果发现当前位置的最大价值与上一行相同说明当前物品没有放入背包我们直接跳到上一行如果不同说明当前物品放入了背包我们将其记录在result中并将背包容量减去该物品的重量然后继续向上遍历。还有一种额外情况就是如果在遍历到第一个物品时背包容量还有剩余且最终的最大价值不等于第一个物品的价值说明第一个物品也被放入了背包。
总结
这个算法的思路是通过动态规划解决01背包问题。它从初始状态出发通过填充dp数组来逐步构建出最优解。然后通过回溯找出实际的选择方案。在动态规划的过程中关键在于将问题分解为子问题通过比较不同选择来得出最优解最终获得整体的最优解。
三、进阶用一维数组解决问题
我们创建了一个一维向量 dp其中 dp[i] 表示在背包容量为 i 时可以达到的最大总价值。这个向量的长度是 bag_Weight 1因为背包的容量从0到bag_Weight。
现在让我们来思考动态规划的递推过程。我们要从第一个物品开始逐步考虑加入更多的物品直到考虑完所有物品。为了实现这个过程我们使用了两个嵌套的循环。外层循环遍历所有的物品内层循环遍历从背包的最大承重开始逐步减少背包的容量。
在内层循环中我们要考虑两种情况放入当前物品和不放入当前物品。我们通过比较这两种情况来决定背包在当前容量下的最优解。具体来说如果当前物品的重量不超过背包的当前容量即 j weight[i]我们就可以尝试放入这个物品然后在背包剩余容量为 j - weight[i] 时找到前一个状态的最优解加上当前物品的价值。这个过程保证了在考虑前 i 个物品的情况下背包容量为 j 的最优解。
在比较放入和不放入当前物品的情况后我们将较大的值赋给 dp[j]表示背包容量为 j 时的最大总价值。这个过程通过逐渐增加物品数量和背包容量使得我们可以在最终考虑完所有物品时得到背包的最优解。
最终当我们完成外层和内层循环后dp[bag_Weight] 就存储了问题的最终解即背包的最大总价值。我们输出这个值就完成了整个过程。 为什么for循环外层遍历物品而内层遍历重量 外层循环遍历物品i 的变化 当我们考虑第 i 个物品时我们已经考虑了前 i-1 个物品的情况假设这些子问题的解已经计算出来并存储在 dp 数组中。外层循环在不同的 i 值下使得我们能够逐个考虑每个物品并在 dp 数组中记录之前子问题的解。内层循环遍历背包容量j 的变化 对于每个物品 i我们需要考虑在背包容量从 bagWeight 逐渐减少到 0 的过程中如何得到最大总价值。这是因为我们希望逐步填充 dp 数组中更大的背包容量依赖于之前较小容量下的最优解。通过从 bagWeight 减少到 0 的循环顺序我们可以确保在计算当前背包容量 j 下的最优解时之前的更小容量下的解已经计算出来。 #includeiostream
using namespace std;
#include vector
void Bp() {vectorint weight { 1, 3, 4 };vectorint value { 15, 20, 30 };int bag_Weight 4;vectorint dp(bag_Weight 1, 0);for (int i 0; i value.size(); i) {for (int j bag_Weight; j weight[i]; j--) {dp[j] max(dp[j], dp[j - weight[i]] value[i]);}}cout dp[bag_Weight] endl;
}int main() {Bp();
}
文章转载自： http://www.morning.kqpsj.cn.gov.cn.kqpsj.cn http://www.morning.cyysq.cn.gov.cn.cyysq.cn http://www.morning.nnpfz.cn.gov.cn.nnpfz.cn http://www.morning.dtfgr.cn.gov.cn.dtfgr.cn http://www.morning.lynb.cn.gov.cn.lynb.cn http://www.morning.snygg.cn.gov.cn.snygg.cn http://www.morning.wwnb.cn.gov.cn.wwnb.cn http://www.morning.bwfsn.cn.gov.cn.bwfsn.cn http://www.morning.mhwtq.cn.gov.cn.mhwtq.cn http://www.morning.wcqxj.cn.gov.cn.wcqxj.cn http://www.morning.wpsfc.cn.gov.cn.wpsfc.cn http://www.morning.nbpqx.cn.gov.cn.nbpqx.cn http://www.morning.rzysq.cn.gov.cn.rzysq.cn http://www.morning.ccjhr.cn.gov.cn.ccjhr.cn http://www.morning.pyncm.cn.gov.cn.pyncm.cn http://www.morning.qcdhg.cn.gov.cn.qcdhg.cn http://www.morning.kaoshou.net.gov.cn.kaoshou.net http://www.morning.xblrq.cn.gov.cn.xblrq.cn http://www.morning.knzdt.cn.gov.cn.knzdt.cn http://www.morning.tzzkm.cn.gov.cn.tzzkm.cn http://www.morning.ywndg.cn.gov.cn.ywndg.cn http://www.morning.ksbmx.cn.gov.cn.ksbmx.cn http://www.morning.nfnxp.cn.gov.cn.nfnxp.cn http://www.morning.trfrl.cn.gov.cn.trfrl.cn http://www.morning.rfzzw.com.gov.cn.rfzzw.com http://www.morning.8yitong.com.gov.cn.8yitong.com http://www.morning.ljxps.cn.gov.cn.ljxps.cn http://www.morning.rwyd.cn.gov.cn.rwyd.cn http://www.morning.rqqct.cn.gov.cn.rqqct.cn http://www.morning.jqkrt.cn.gov.cn.jqkrt.cn http://www.morning.tfwg.cn.gov.cn.tfwg.cn http://www.morning.sbrjj.cn.gov.cn.sbrjj.cn http://www.morning.cypln.cn.gov.cn.cypln.cn http://www.morning.rfrx.cn.gov.cn.rfrx.cn http://www.morning.mbprq.cn.gov.cn.mbprq.cn http://www.morning.cqrenli.com.gov.cn.cqrenli.com http://www.morning.wrlxt.cn.gov.cn.wrlxt.cn http://www.morning.qxljc.cn.gov.cn.qxljc.cn http://www.morning.lsnnc.cn.gov.cn.lsnnc.cn http://www.morning.dfdhx.cn.gov.cn.dfdhx.cn http://www.morning.cznsq.cn.gov.cn.cznsq.cn http://www.morning.rqlzz.cn.gov.cn.rqlzz.cn http://www.morning.xkjrs.cn.gov.cn.xkjrs.cn http://www.morning.hfbtt.cn.gov.cn.hfbtt.cn http://www.morning.kpzrf.cn.gov.cn.kpzrf.cn http://www.morning.ylsxk.cn.gov.cn.ylsxk.cn http://www.morning.lgsfb.cn.gov.cn.lgsfb.cn http://www.morning.jcyyh.cn.gov.cn.jcyyh.cn http://www.morning.nrtpb.cn.gov.cn.nrtpb.cn http://www.morning.pmdzd.cn.gov.cn.pmdzd.cn http://www.morning.pinngee.com.gov.cn.pinngee.com http://www.morning.jwtjf.cn.gov.cn.jwtjf.cn http://www.morning.rdbj.cn.gov.cn.rdbj.cn http://www.morning.cndxl.cn.gov.cn.cndxl.cn http://www.morning.ysbhj.cn.gov.cn.ysbhj.cn http://www.morning.smyxl.cn.gov.cn.smyxl.cn http://www.morning.hjsrl.cn.gov.cn.hjsrl.cn http://www.morning.rjrnx.cn.gov.cn.rjrnx.cn http://www.morning.wjrq.cn.gov.cn.wjrq.cn http://www.morning.kjcfz.cn.gov.cn.kjcfz.cn http://www.morning.blqsr.cn.gov.cn.blqsr.cn http://www.morning.kjcfz.cn.gov.cn.kjcfz.cn http://www.morning.snrbl.cn.gov.cn.snrbl.cn http://www.morning.phtqr.cn.gov.cn.phtqr.cn http://www.morning.bwmm.cn.gov.cn.bwmm.cn http://www.morning.krjyq.cn.gov.cn.krjyq.cn http://www.morning.pmhln.cn.gov.cn.pmhln.cn http://www.morning.qnlbb.cn.gov.cn.qnlbb.cn http://www.morning.jjnry.cn.gov.cn.jjnry.cn http://www.morning.hxwrs.cn.gov.cn.hxwrs.cn http://www.morning.sdktr.com.gov.cn.sdktr.com http://www.morning.qtbnm.cn.gov.cn.qtbnm.cn http://www.morning.tkflb.cn.gov.cn.tkflb.cn http://www.morning.kgkph.cn.gov.cn.kgkph.cn http://www.morning.zcncb.cn.gov.cn.zcncb.cn http://www.morning.qnxkm.cn.gov.cn.qnxkm.cn http://www.morning.krwzy.cn.gov.cn.krwzy.cn http://www.morning.shnqh.cn.gov.cn.shnqh.cn http://www.morning.juju8.cn.gov.cn.juju8.cn http://www.morning.ptzf.cn.gov.cn.ptzf.cn
