贪心法.doc

课
程
设
计
报
告
课程:算法设计与分析
班级: 08计算机2班
学号: 0082900
姓名: 叶小玉
完成时间:2010-12-31
0/1背包问题
设计目的
掌握贪心法的原理及使用环境。
掌握动态规划法的原理及使用环境;
掌握分枝限界法的原理及使用环境;
分析三种算法的特点。
设计内容
1. 任务描述
0/1背包问题简介
已知一个载重为M的背包和n件物品,第i件物品的重量为 Wi,如果将第i件物品全部装入背包,将有收益Pi(Wi>0,Pi>0,0£i<n)。求一种最佳装载方案,使得收益最大。如果每一件物品不能分割,只能作为整体或者装入背包,或者不装入,称为 0/1背包问题。
2)设计任务简介
设计使用贪心法、动态规划法、分枝限界法求解0/1背包问题设计对算法或程序的测试方案并完成测试。
测试数据:设有载重能力M=20的背包,3件物品的重量为:(w0,w1,w2)=(8,9,15),物品装入背包的收益为:(p0,p1,p2)=(12,15,10)


0/1背包五难题的符号化表示是,给定M>0,Wi>0 ,Vi>0,,要求找
一个n元0-1向量(X1,X2,...,Xn),Xi=0或1,,使得
而且到最大。
数学模型为:max
约束条件

Xi=0或1,




贪心算法采用逐步构造最优解的方法,在每个阶段,都在一定的标准下做出
一个看上去最优的决策,0/1背包选择单位效益最高贪心准则,即从剩余物
品中选择可装入包的Pi/Wi值最大的物品。
主要模块说明
void bagloading(int x[],float p[],float w[],float M,int n,int hao[])
{
float t,k,pw[num];
int i,j,m,kk,q;
for(i=0;i<n;i++)
pw[i]=p[i]/w[i];//计算价格质量比
m=n-1;
while (m>0)
{
kk=0;
for(j=0;j<m;j++)
if (pw[j]<pw[j+1])
冒泡排序,时间复杂度为
{
q=hao[j];
hao[j]=hao[j+1];
hao[j+1]=q;
t=p[j];
p[j]=p[j+1];
p[j+1]=t;
k=w[j];
w[j]=w[j+1];
w[j+1]=k;
kk=j;
}
m=kk;
}
//按p/w次序从大到小选择物品
i=0;
while(i<n&&(w[i]<=M))
{
x[i]=1;
M-=w[i];
i++;
}
}
算法分析
贪心法解决0/1背包问题主要代价是花费在p/w的排序上。由程序可以知道
冒泡排序的时间复杂度为。它也是整个程序的时间复杂度。贪心法
可以很快的解决问题,但是它不一定能够得到最优解,寻找一个好的贪心法
则在贪心法处理中是至关重要的。


测试结果与分析
结果截图:
贪心法处理该数据得到的解是最优解。但是不是所有的数据应用贪心法都能
够得到最优解。
利用动态规划法求解0/1背包问题


对于0/1背包问题,可以通过做出变量X1,X2,...Xi的一个决策序列来得到它
的解。而对变量X的决策就是决定它的取值。假定决策这些X的次序为
Xn,Xn-1,..., Xn做出决策之后,问题处于下面两种状态之一:
背包的剩余容量是W,没有产生效益; 剩余容量是M-m,效益增长了P。
剩余下来对Xn-1,Xn-2,...,X1的决策相对于决策 X所产生的问题状态是
最优的。设


主要模块说明
void knapsack(int val[],int wei[],int M,int n,int**m) //二维数组m存储最优子决策
{
int jmax=min(wei[n]-1,M);
for(int j=0;j<=jmax;j++)
m[n][j]=0;
for(int jj=wei[n];jj<=c;jj++)
m[n][jj]=val[n];
for(int i=n-1;i>1;i--){ //递归部分
jmax=min(wei[i]-1,M);
for(int j=0;j<=jmax;j++)
动态规划思想--寻找最优决策
m[i