网站建设中怎样设置背景,暗红色网站,阿里云服务器做网站安全吗,苍南哪里有网站建设公司1. 前言
背包问题是类型问题#xff0c;通过对这一类型问题的理解和掌握#xff0c;从而可以归纳出求解此类问题的思路和模板。
背包问题的分类有#xff1a;
0-1背包问题#xff0c;也称为不可分割背包问题。无限背包问题。判定性背包问题.带附属关系的背包问题。双背包…1. 前言
背包问题是类型问题通过对这一类型问题的理解和掌握从而可以归纳出求解此类问题的思路和模板。
背包问题的分类有
0-1背包问题也称为不可分割背包问题。无限背包问题。判定性背包问题.带附属关系的背包问题。双背包求最优值.构造三角形问题.带上下界限制的背包问题(012背包)……
本文将介绍0-1背包问题的各种求解方案通过对各种求解方案的研究从而全方面了解0-1背包问题的本质。
2. 0-1 背包问题
问题描述
有一背包能容纳的重量为 m现有 n种物品每种物品有重量和价值 2 个属性。请设计一个算法在不分割物品的情况下保证背包中所容纳的物品的总价值是最大的。
0-1背包也称为完全背包或不可分割背包问题是一类常见的背包问题。常用的实现方案有递归和动态规划 。
2.1 递归算法
可以有 3 种写法。
2.1.1 第一种递归回溯方案
回顾递归回溯算法适合的问题域
待解决的问题可以分多步。如迷宫问题、排列组合问题……每一步都可能存在多个选择当某一个选择行不通或此选择结束后可以回溯到上一步再另行选择。
那么背包问题是否适合上述的要求
可以想象背包里有很多个格间。当每一个格间填充完毕则表示得到一种求解。对于格间而言每一种物品都是一种选择可以通地回溯再选择另一个物品。其本质是对物品进行任意组合然后再选择总价值最大的一种组合。
如下图有 3 个物品需要放置入容量为 50 的背包中。初始可把背包想象成一个大格间此时可以试着放入物品中的一个。 物品放入格间的条件
物品不曾在背包中。物品的重量小于或等于背包现有容量。
如下图把物品一放入背包中。且把背包剩下空间想象为一个格间在余下的物品中选择一个放入此格间中。 如下把物品二放入格间中。 因物品一和物品二的重量之和为 50。等于背包总容量。此时背包中已经没有剩余空间。也意味着不能再向此背包中放入物品。
至此可以输出背包中的物品且把背包中的总价值 180 存储在全局变量中以便在后续操作时查找是否还有比此值更大的值。
回溯物品
所谓回溯物品指把物品从背包中移走试着再放入一个其它物品。
如下图回溯物品二腾出格间。因物品三满足放入条件放入格间。 此时背包还有剩余空间同样把剩余空间想象成一个格间。因有剩余空间可以试着把物品二放入背包中。 但因物品二的重量大于背包已有的容量不能放入。此时可以输出背包中的物品信息并记录背包中的最大价值为110。因比前面的180的值小继续保留 180这个价值为当前最大值。
对上述流程做一个简单总结 当背包还有空间且有物品可以放入时则加入到背包中。 当背包不再能放下任何一件物品时计算此时的总价值并确定是不是最大价值。 Tips这里有一点需要注意递归函数的出口有 2 个一是还有物品可选择但不能放入背包中。二是不再有物品可供选择。 回溯当前已经放入物品选择其它物品重复上述过程一直到找到真正的最大值。
代码如下所示
#includebits/stdc.h
using namespace std;
struct Goods {//重量int weight;//价值int price;//装入状态bool isUse;
};
/*
*初始化
*/
Goods allGoods[3] { {20,60,false},{30,120,false},{10,50,false}};//背包重量
int weight50;
//最大价值
int maxPrice0;
//总价值
int totalPrice0;
/*
* 0-1 背包
* idx:物品编号只需要考虑组合
* deep:递归深度
*/
void bag(int idx,int deep,int weight) {//每次都可以从所有物品中进行选择for(int iidx; i3; i) {if( allGoods[i].isUsefalse ) {//物品不曾放入背包if( allGoods[i].weightweight) {//且可以放下增加背包中的总价值totalPriceallGoods[i].price;//标志此物品已经放入allGoods[i].isUsetrue;//继续放置物品bag(i,deep1,weight - allGoods[i].weight);//回溯totalPrice-allGoods[i].price;allGoods[i].isUsefalse;} else {//出口一不可以放下计算此时背包中的物品的价值是否是最大值cout-----------查询到某个物品不能放下时显示背包中信息------------endl;if(totalPricemaxPrice) maxPrice totalPrice;for(int j0; j3; j)if(allGoods[j].isUse)coutallGoods[j].weight,allGoods[j].priceendl;return ;}}}//出口二不再有物品可以选择cout--------当没有物品可选择时也要显示背包中物品信息-----------endl;if(totalPricemaxPrice) maxPrice totalPrice;cout此时背包中物品endl;for(int j0; j3; j)if(allGoods[j].isUse)coutallGoods[j].weight,allGoods[j].priceendl;
}
//测试
int main() {bag(0,1,weight);cout---------------------endl;cout最终背包中最大价值maxPriceendl;return 0;
}测试结果 2.1.2 第二种回溯方案
第一种回溯方案略显复杂可以采用下面的回溯方案。
此方案中把物品可放入和不可放入做为选择。但其本质和上述实现是一样的。
#includebits/stdc.h
using namespace std;
struct Goods {//物品重量int weight;//物品价值int value;//物品状态 1 已经使用0 未使用int isUse;
};//最大价值
int maxPrice0;
//总价值
int totalPrice0;
//背包重量
int bagWeight100;
//物品信息
Goods allGoods[5] { {20,60,false},{30,120,false},{10,50,false},{20,20,false},{40,100,false} };
int count4;
/*
*显示背包中物品
*/
void showBag() {for(int i0; i5; i) {if(allGoods[i].isUse)coutallGoods[i].weight,allGoods[i].valueendl;}
}
/*
* idx: 物品编号
* count: 物品总数量
*/
void zeroAndOneBag(int idx,int weight) {//物品只有两种状态for(int i0; i1; i) {if( weight-allGoods[idx].weight*i0 ) {//物品状态allGoods[idx].isUsei;//总价值totalPriceallGoods[idx].value*i;if(idx4) {if(totalPricemaxPrice) {maxPricetotalPrice;cout------------endl;showBag();coutmaxPriceendl;}} else {zeroAndOneBag(idx1,weight-allGoods[idx].weight*i);}//回溯allGoods[idx].isUse0;totalPrice-allGoods[idx].value*i;}}
}
//测试
int main() {zeroAndOneBag(0,bagWeight);return 0;
}2.1.3 第三种方案
前两种方案不仅可得到最优值且可以得到寻找过程中的各种组合方案。如果仅仅是想得到最终结果不在乎中间的过程则可以使用下面的递归方案。
#includeiostream
#includewindows.h//max函数
using namespace std;
struct Goods {//重量int weight;//价值int price;//装入状态bool isUse;
};
//所有物品
Goods allGoods[5] { {20,60,false},{30,120,false},{10,50,false},{20,20,false},{40,100,false} };
//背包重量
int bagWeight 100;
//物品总数量
int totalNumber 5;
/*
*递归
*/
int zeroAndOneBag(int index, int remainWeight) {int totalPrice 0;//没有物品可放if (index totalNumber) return 0;if (allGoods[index].weight remainWeight)//当前物品不能放入查看其它物品放入的情况totalPrice zeroAndOneBag(index 1, remainWeight);else//当前物品可以放入则在把此物品放入和不放入背包时的最大价值 totalPrice max(zeroAndOneBag(index 1, remainWeight -allGoods[index].weight) allGoods[index].price, zeroAndOneBag(index 1, remainWeight));return totalPrice;
}
//测试
int main() {int value zeroAndOneBag(0, bagWeight);cout value endl;return 0;
}2.2 动态规划
背包问题有 2 个状态值背包的容量和可选择的物品。
物品对于背包而言只有 2 种选择要么装下物品要么装不下如下图所示表格的行号表示物品编号列号表示背包的重量。单元格中的数字表示背包中最大价值。当物品只有一件时当物品重量大于背包容量不能装下反之能装下。如下图物品重量为 1。无论何种规格容量的背包都能装下假设背包的容量至少为 1。 如下图当增加重量为 2 的物品后当背包的容量为 1 时不能装下物品则最大值为同容量背包中已经有的最大值。 但对容量为 2的背包而言恰好可以放入新物品此时背包中的最大价值就会有 2 个选择一是把物品 2 放进去背包中的价值为 3。二是保留背包已有的价值4。然后在两者中选择最大值 4。 当背包容量是 3时物品2也是可以放进去的。此时背包的价值可以是当前物品的价值 3加上背包剩余容量3-21能存放的最大价值4计算后值为 7。要把此值和不把物品放进去时原来的价值 4 之间进行最大值选择。 所以对于背包问题核心思想就是
如果物品能放进背包则先计算出物品的价值加上剩余容量能存储的最大价值之和再找到不把物品放进背包时背包中原有价值。最后在两者之间进行最大值选择。当物品不能放进背包显然保留背包中原来的最大价值信息。
2.3.3 编码实现
#include iostream
#include vector
using namespace std;
int main(int argc, char** argv) {//物品信息int goods[3][3] { {1,4},{2,3} };//背包容量int bagWeight0;cout请输入背包容量endl;cinbagWeight;//状态表int db[4][bagWeight1] {0};for(int i0; i4; i) {for(int j0; jbagWeight1; j) {db[i][j]0;}}for(int w1; w4; w) {for(int wt1; wtbagWeight; wt) {if( goods[w-1][0]wt ) {//如果背包不能装下物品保留背包上一次的结果db[w][wt]db[w-1][wt];} else {//能装下,计算本物品价值和剩余容量的最大价值int valgoods[w-1][1] db[w-1][ wt- goods[w-1][0] ];//背包原来的价值int val_ db[w-1][wt];//计算最大值db[w][wt]valval_?val:val_;}}}for(int i1; i3; i) {for(int j1; jbagWeight; j) {coutdb[i][j]\t;}coutendl;}return 0;
}输出结果 3. 总结
本文主要讲解背包系列 中的0-1背包问题。0-1背包问题可以使用递归和动态规划方案得到其解。
