第22章背包问题求解

《第22章背包问题求解》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第22章背包问题求解问题描述问题分析及实现开发过程常见问题及解决第22章背包问题求解问题描述问题分析及实现开发过程常见问题及解决第22章背包问题求解问题描述问题分析及实现开发过程常见问题及解决第22章背包问题求解问题描述问题分析及实现开发过程常见问题及解决背包问题求解生活中，少不了算法。比如，出外旅行，需要带随身物品，但有些不是在旅行过程中必须的，但另外有些物品是必须的。那么，人们是不是会想都不想，就把物品装上了呢？答案是否定的。本章将简介像这类的问题的求解。需要注意的是，本章的背包问题求解，也是数据结构与算法中经典的一例。22.1问题描述有N件物品和一个容量为V的背包，

2、第i件物品的费用是c，价值是w，求解将哪些物品装入背包可使这些物品的容量总和不超过背包容量，且价值总和最大。22.2问题分析及实现22.2.1问题分析22.2.2问题实现22.2.3程序运行22.2问题分析及实现由问题描述可知，我们要实现的是从N件物品中，找出价值总合最大，但又不超过背包容量K的值的解。简单举例：有两件物品，价值分别是30，20，重量分别是30，30，背包容量K为30，此时，我们的解应该是30重量，30价值的物品。22.2.1问题分析我们的将要开发的程序，就是采用一定算法，取得最优解，即，重量不超过背包容量，但取得的价值最大。为了能够实现这一算法，最简单实

3、用的编程方法就是采用递归的方式调用，即，把复杂度为N的问题，采用复杂度为N-1的方式来表示和计算，当问题的规模小到不能再小时，结果就很轻易地计算得出最终的解了。在计算机程序设计方面，递归是一把双刃剑，用好递归，可使程序设计难度降低一半以上。但用不好，反受其累。22.2.2问题实现1.采用结构体保存过程数据。通过定义一个结构体类型，记录物品的价值和重量。那么，根据这个思路，代码如下（代码22-1.txt）。22.2.2问题实现01#include02#defineN100/*物品总种数*/03intnType;/*物品种数*/04intcurrentopt

4、ion[N];/*当前解*/05intoption[N];/*所有解的集合*/06doubleMaxvalue;/*总价值*/07doubletotalValue;/*输入的全部物品的总价值*/08doublelimitW;/*输入的限制总重量*/09struct/*物品结构*/10{11doubleweight;12doublevalue;13}good[N];22.2.2问题实现2.递归主函数此函数主要以递归调用的方式，判断并找出一个最优解。递归的方式，就是函数自己以不同的参数值，再一次调用自己，直到这个函数返回至最顶层调用级。代码如下（代码22-2.txt）。22.

5、2.2问题实现01voidCheckOut(inti,doubletw,doubletotalvalue)02{03intk;04if(tw+good[i].weight<=MaxWeight)05{06currentoption[i]=1;07if(i

6、;17if(totalvalue-good[i].value>Maxvalue)18{19if(i

7、然后调用递归函数计算最优解，并在最后输出解。代码如下（代码22-3.txt）。22.2.2问题实现01/*背包问题主函数*/02voidmain()03{04inti;05doubleweight,value;06printf("请输入物品类别个数:");07scanf("%d",&nType);08printf("请输入各物品的重量和价值:");09totalValue=0.0;10for(i=0;i