seo神马网站推广器,网站建设div可拖拽布局,外贸模板建站,用wordpress做网站页面显示404文章目录 1. 题目描述2. 算法思路3. 例题分析4. 代码编写 1. 题目描述 对于给定的 n n n 个物品#xff0c;第 i i i 个物品的重量为 W i W_i Wi#xff0c;价值为 V i V_i Vi#xff0c;对于一个最多能装重量 c c c 的背包#xff0c;应该如何选择放入包中的物品… 文章目录 1. 题目描述2. 算法思路3. 例题分析4. 代码编写 1. 题目描述 对于给定的 n n n 个物品第 i i i 个物品的重量为 W i W_i Wi价值为 V i V_i Vi对于一个最多能装重量 c c c 的背包应该如何选择放入包中的物品使得包中物品的总价值最大
2. 算法思路 1. 将问题转化为 2. 按照上述思路先将各物品按照单位价值递减的顺序排序其次进行判断是否在承重范围值内。 定义 c w cw cwcurrent weight表示当前重量 c p cp cpcurrent price表示当前价值。 根节点代表扩展结点 其余每一层代表一个物品越靠近根节点单位价值越高。选中该物品即搜索左子树进行判断。具体执行操作如下所示 1先计算所有物品的单位价值将其进行降序排列。 2排列之后从根节点(扩展节点)出发。 3搜索左子树判断是否满足约束条件(物品是否装入背包) 若选中该物品可行解cww[i]cpp[i]继续向下遍历直至遇到不可行解时开始向上回溯取出最后一个装入的物品进入右子树。4进入右子树首先计算当前节点的上界bound(i) 若bound(i)小于bestp剪去右子树继续向上回溯否则进行步骤3。5遇到叶子节点比较当前价值与bestp若cpbestp则bestp进行更新。 6直到遍历完所有的节点除剪枝部分外。
3. 例题分析 1. 例题1(手写) 2. 例题2假设 n 3 n3 n3有三件物品三个物品的重量为 20 、 15 、 10 {20、15、10} 20、15、10三个物品的价值为 20 、 30 、 25 {20、30、25} 20、30、25对于一个最大承重为 25 25 25 的背包求包中物品的组合最大的价值是多少 3. 例题2分析过程对三件物品分别进行编号 1 2 3 123 123。初始情况背包是空的。 1首先我们把 1 1 1 号物品放进背包里此时背包里只有一件物品总重量为 0 20 20 02020 02020没有超过承重 25 25 25因此可以将 1 1 1 号物品成功放入背包内。 2接下来尝试把 2 2 2 号物品放入背包内但是发现包中 1 1 1 号物品和 2 2 2 号物品的重量和为 20 15 35 201535 201535超过了承重 25 25 25因此不能把 2 2 2 号物品放入背包内。 3接着考虑 3 3 3 号物品此时包中只有 1 1 1 号物品。发现 1 1 1 号物品和 3 3 3 号物品的重量和为 20 10 30 201030 201030超过了承重 25 25 25因此 3 3 3 号物品也不能放入背包内。 4由于只有 3 3 3 件物品并且对于每一种物品我们都考虑过是否将其放入背包内也就是找到了一种基本情况。找到一个基本情况后我们就可以看看包里的物品的总价值了。这里包里只有一个 1 1 1 号物品因此总价值为 20 20 20。 5重点来了回溯过程每次找出一种满足条件的基本情况就进行一次回溯找到最后放入包中的物品并将其取出接着考虑是否放入编号在这个物品之后的第一个物品。这里我们就把 1 1 1 号物品取出接下来考虑是否放入 2 2 2 号物品。 6取出 1 1 1 号物品后背包是空的此时如果放入 2 2 2 号物品背包总重量为 15 15 15没有超过背包承重因此把 2 2 2 号物品放入背包内。 7类似地考虑将 3 3 3 号物品放入背包内。由于 2 2 2 号物品和 3 3 3 号物品的重量和为 15 10 25 151025 151025没有超过承重 25 25 25因此将其放入背包内。 8由于考虑完了 3 3 3 号物品因此又找到了一个基本情况记下此时包里物品的总价值为 30 25 55 302555 302555。由于 55 55 55 高于上一种基本情况的总价值因此将最优解更新为 55 55 55。 9进行一次回溯取出背包中最后放入的物品也就是 3 3 3 号物品。但是注意当最后放入背包中的物品恰好是编号最大的物品时需要额外进行一次回溯。为什么呢因为编号最大的物品之后已经没有编号更大的物品了因此没有可以考虑的下一种情况只能在上一个层面上在进行一次回溯才能产生可能的最优解此处不必考虑只放入2号物品的情况因为一定不是最优解原因可以自己思考一下。 这里再回溯一次也就是将倒数第二个放入包中的物品取出来这里就取出 2 2 2 号物品。先后取出 3 3 3 号物品和 2 2 2 号物品之后包应该处于空的状态。 10上一步中取出了 2 2 2 号物品因此这一步直接考虑能否放入 3 3 3 号物品简单的判断后即可得出可以放入并且同上理也可以得出这是一种基本情况。但是由于包中只有 3 3 3 号物品总价值为 25 25 25没有超过当前的最优解 55 55 55因此将该情况忽略。 11最后一次回溯取出包中的 3 3 3 号元素。由于此时包已经空了并且最后一次取出的是编号最大的元素那么说明算法已经完成了所有情况的遍历算法终止 55 55 55 是最优解。
4. 代码编写
// n5, c10, w{2, 2, 6, 5, 4}, v{6, 3, 5, 4, 6}的0-1背包问题的最优解和最优值。
#include iostream
using namespace std;#define N 10
int w[N]; //重量
int v[N]; //价值
int x[N]; //1表放入背包0表不放入
int n,c; //n物品个数 c背包的最大容量int cw0; //当前物品总重
int cv0; //当前物品总价值int bestp0; //当前最大价值
int bestx[N]; //最优解//回溯函数 k表示当前处在第几层做选择k1时表示决定是否将第一个物品放入背包
void backtrack(int k)
{//叶子节点输出结果if(kn){//找到一个更优的解if(cvbestp){ //保存更优的值和解bestp cv;for(int i1; in; i)bestx[i] x[i];}}else{//遍历当前节点的子节点for(int i0; i1; i){x[k]i;if(i0){backtrack(k1);}else{ //约束条件当前物品是否放的下if((cww[k])c){cw w[k];cv v[k];backtrack(k1);cw - w[k];cv - v[k];}}}}
}int main()
{cout请输入物品的个数;cinn;cout请输入每个物品的重量及价值:endl;for(int i1;in;i){cinw[i]v[i];}cout请输入背包的限制容量;cinc;backtrack(1);cout最优值是:bestpendl;cout(;for(int i1;in;i){coutbestx[i] ;} cout);return 0;
}
