学计算机去哪个职业学校,seo推广特点,荥阳市建设局 网站,个人网站可以做导购吗文章目录1. 问题描述2. 回溯解决思路1. 问题描述
0-1背包非常经典#xff0c;很多场景都可以抽象成这个问题。经典解法是动态规划#xff0c;回溯简单但没有那么高效。
有一个背包#xff0c;背包总的承载重量是 W kg。现有n个物品#xff0c;每个物品重量不等#xff0…
文章目录1. 问题描述2. 回溯解决思路1. 问题描述
0-1背包非常经典很多场景都可以抽象成这个问题。经典解法是动态规划回溯简单但没有那么高效。
有一个背包背包总的承载重量是 W kg。现有n个物品每个物品重量不等并且不可分割。选择几件物品装到背包中。在不超过背包所能装载重量的前提下如何让背包中物品总重量最大物品是不可分割的要么装要么不装所以叫 0-1背包问题。
2. 回溯解决思路
对于每个物品来说都有两种选择装进背包或者不装进背包。对于n个物品来说总的装法就有 2n 种去掉总重量超过 W kg的从剩下的装法中选择总重量最接近 W kg的。不过我们如何才能不重复地穷举出这 2n 种装法呢
可以用回溯方法。
把物品依次排列整个问题就分解为了n个阶段每个阶段对应一个物品怎么选择。先对第一个物品进行处理选择装进去或者不装进去然后再递归地处理剩下的物品。当发现已经选择的物品的重量超过 W kg之后就停止继续探测剩下的物品(搜索剪枝技巧)。
/*** description: 0-1背包--回溯应用* author: michael ming* date: 2019/7/9 1:13* modified by: */
#include iostream
#define MaxWeight 76 //背包承载极限
using namespace std;
void fill(int i, int curWeight, int *bag, int N, int maxweightinbag)
{if(curWeight MaxWeight || i N)//到达极限了或者考察完所有物品了{if(curWeight maxweightinbag)maxweightinbag curWeight;//记录历史最大装载量return;}fill(i1,curWeight,bag,N,maxweightinbag);//不选择当前i物品cw不更新if(curWeightbag[i] MaxWeight)//选择当前i物品cw更新{//没有达到极限继续装fill(i1,curWeightbag[i],bag,N,maxweightinbag);}
}
int main()
{const int N 4;int bag[N] {15,6,40,21};
// int bag[N] {1,2,3,4};int maxweightinbag 0;fill(0,0,bag,N,maxweightinbag);cout 最大可装进背包的重量是 maxweightinbag;return 0;
}升级版 每个物品对应着一种价值求不超过背包载重极限可装入背包的最大总价值。在上面程序里稍加修改即可
/*** description: * author: michael ming* date: 2019/7/11 20:42* modified by: */#include iostream
#define MaxWeight 50 //背包承载极限
using namespace std;
void fill(int i, int curWeight, int curValue, int *bag,int *value, int N, int weightinbag, int maxValue)
{if(curWeight MaxWeight || i N)//到达极限了或者考察完所有物品了{if(curValue maxValue){maxValue curValue;//记录历史最大价值weightinbag curWeight;//记录最大价值对应的重量}return;}fill(i1,curWeight,curValue,bag,value,N,weightinbag,maxValue);//不选择当前i物品cw,cv不更新if(curWeightbag[i] MaxWeight)//选择当前i物品cw,cv更新{//没有达到极限继续装fill(i1,curWeightbag[i],curValuevalue[i],bag,value,N,weightinbag,maxValue);}
}
int main()
{const int N 4;int bag[N] {15,6,40,21};int value[N] {1,2,3,4};int weightinbag 0, maxValue 0;fill(0,0,0,bag,value,N,weightinbag,maxValue);cout 最大可装进背包的最大价值是 maxValue ,对应重量是: weightinbag;return 0;
}
