《程序设计综合实践》课件_2.3.2 回溯法 - 01背包问题.pptx

1、3.1 0-1背包问题1 0-1背包问题也是算法设计中的经典问题。0-1背包问题：给定一组n个物品，每种物品都有自己的重量和价值，所有物品的重量和价值都是非负的，第i个物品的重量为wi，价值为pi，背包所能承受的最大重量为W，如何选择，才能使得物品的总价值最高？问题的名称来源于如何选择最合适的若干物品放置于给定背包中，相似问题经常出现在商业、组合数学、计算复杂性理论、密码学和应用数学等领域中。任何物品都有选择或不选择两种可能，不考虑总价值最高情况下，总可选方案数为 。按照贪心法思路，将物品按单位重量价值递减次序排队，先优先选择单位重量价值高的物品，在不超出总重量的前提下，获得一种选择方案和它相

2、应总价格，这样的方案并不能保证是最优解。2n2 我们可以用试探-回溯法解决0-1背包问题，试探每一个物品是否放入背包。为了提高算法效率，我们需要结合贪心法思想，尽量快速找出比较优的方案，这样，我们可以在试探-回溯过程中，判断出在当前选择状态下，预估背包剩余容量摆放剩余物品可能达到的最大值，如果背包里已有物品总价值加上这个预估值也无法超过现有最优方案，就放弃继续往下试探，直接回溯，减去不必要树枝，减少状态空间树的结点数，优化算法。试探完所有物品，到达状态空间树叶子结点位置时，获得一种摆放方案，如果这一方案优于原最优方案，则替换原最优方案。无论何种情况，都需要继续回溯；回溯退回到最初出发状态时，现

3、有最优方案就是最佳方案。3主要数据结构设计：#define MaxN 500struct SGoods int iWeight;/商品重量 int iPrice;/商品价值 double dPriceRatio;/每单位重量的价值;struct SSolution int bSelectA MaxN;/选中状态 int iMaxValue;/总价值;4（待续）struct SBag int N;/物品数量 int iWeightLimit,iWeightLeft;/背包容量，剩余容量 struct SGoods sGoodsA MaxN;/物品信息 struct SSolution bestS

4、olution,solutionNow;/最优解、目前解;5主要模块：/初始化问题,成功返回1，失败返回0int InitProbelm(struct SBag *pProblem);/打印最优解void PrintSolution(struct SBag *pProblem);/试探第i个物品选择void Try(struct SBag *pProblem,int i);/检查目前第i个皇后摆放是否okint CheckOk(struct SBag *pProblem,int i);6/初始化问题,成功返回1，失败返回0int InitProbelm(struct SBag *pProble

5、m)int iWeightLimit;printf(“请输入背包限重(101000):n);scanf(%d,&iWeightLimit);if(iWeightLimit 1000)return 0;pProblem-iWeightLeft=pProblem-iWeightLimit=iWeightLimit;int n;printf(请输入物品数量(4500):n);scanf(%d,&n);if(n 500)return 0;7（待续）pProblem-N=n;printf(请依次输入各物品重量和价值(空格分隔):n);int i;for(i=0;i N;+i)struct SGoods

6、goods;scanf(%d%d,&goods.iWeight,&goods.iPrice);/计算商品单位价值 goods.dPriceRatio=(double)goods.iPrice/goods.iWeight;pProblem-sGoodsA i=goods;pProblem-bestSolution.bSelectA i=pProblem-solutionNow.bSelectAi=0;pProblem-bestSolution.iMaxValue=pProblem-solutionNow.iMaxValue=0;8（待续）/按商品单位价值递减排序 qsort(pProblem-s

7、GoodsA,pProblem-N,sizeof(struct SGoods),compare);return 1;/商品单位价值比较函数，快速排序函数qsort递减排序用int compare(const void*p1,const void*p2)const struct SGoods*pGoods1=(const struct SGoods*)p1;const struct SGoods*pGoods2=(const struct SGoods*)p2;if(pGoods1-dPriceRatio pGoods2-dPriceRatio)return-1;/商品单位价值比较高排前面 el

8、se if(pGoods1-dPriceRatio=pGoods2-dPriceRatio)return 0;else return 1;9/打印最优解void PrintSolution(struct SBag *pProblem)int i,count=0;printf(最大总价值%d:n,pProblem-bestSolution.iMaxValue);for(i=0;i N;+i)if(pProblem-bestSolution.bSelectA i)+count;printf(No.%d,重量:%d,价值%dn,count,pProblem-sGoodsA i.iWeight,pPr

9、oblem-sGoodsA i.iPrice);10void Try(struct SBag *pProblem,int i)/试探第i个物品选择 if(i pProblem-N)/已试探完所有物品 if(pProblem-bestSolution.iMaxValue solutionNow.iMaxValue)pProblem-bestSolution=pProblem-solutionNow;/替换成更优解 return;/继续回溯 int iSelected;for(iSelected=1;iSelected=0;-iSelected)/单位价值物品先试放 pProblem-soluti

10、onNow.bSelectA i-1=iSelected;if(pProblem-solutionNow.bSelectA i-1)/放入时设置状态 pProblem-iWeightLeft-=pProblem-sGoodsA i-1.iWeight;pProblem-solutionNow.iMaxValue+=pProblem-sGoodsA i-1.iPrice;11（待续）if(CheckOk(pProblem,i)/本次试探是否可行 Try(pProblem,i+1);/继续试探摆放下个物品 if(pProblem-solutionNow.bSelectA i-1)/恢复不放入状态，

11、回溯 pProblem-solutionNow.bSelectA i-1=0;pProblem-iWeightLeft+=pProblem-sGoodsA i-1.iWeight;pProblem-solutionNow.iMaxValue-=pProblem-sGoodsA i-1.iPrice;12/检查目前第i个物品摆放是否okint CheckOk(struct SBag *pProblem,int i)if(pProblem-iWeightLeft bestSolution.iMaxValue-pProblem-solutionNow.iMaxValue;/物品按单位价值递减排序 i

12、f(i+1 N&pProblem-iWeightLeft*pProblem-sGoodsA i.dPriceRatio=iValue)return 0;/后面物品继续摆放已无法超过已有最佳方案 return 1;/ok13int main()struct SBag theProblem;if(InitProbelm(&theProblem)Try(&theProblem,1);/从第一个物品开始试探 PrintSolution(&theProblem);/打印最优解 return 0;14程序运行情况如下：请输入背包限重(101000):200请输入物品数量(4500):8请依次输入各物品重量和价值(空格分隔):79 8358 1486 5411 8528 7262 5215 4868 62最大总价值 340:No.1,重量:11,价值 85No.2,重量:15,价值 48No.3,重量:28,价值 72No.4,重量:79,价值 83No.5,重量:62,价值 5215