用蛮力法、动态规划法和贪心法求
解01背包问题(总13页)
-本页仅作为预览文档封面，使用时请删除本页-
算法设计与分析
项 目 名 称：用蛮力法、动态规划法和贪心法求解0/1背包问题
作者姓名：余武丹
李红波 刘红梅
完成日期：2013年9月20日
2
目录
第一章：简介（Introduction）
第二章：算法定义（Algorithm Specification）
第三章：测试结果（Testing Results）
第四章：分析和讨论
3
第一章：简介（Introduction）
0/1背包问题是给定n个重量为{w1, w2, … ,wn}、价值为{v1, v2, … ,vn}的物品和一个容量为C的背包，求这些物品中的一个最有价值的子集，并且要能够装到背包中。
在0/1背包问题中，物品i或者被装入背包，或者不被装入背包，设xi表示物品i装入背包的情况，则当xi=0时，表示物品i没有被装入背包，xi=1时，表示物品i被装入背包。根据问题的要求，有如下约束条件和目标函数：
nwixiCi1xi{0,1}(1in)（式1）
maxvixii1n（式2）
于是，问题归结为寻找一个满足约束条件式1，并使目标函数式2达到最大的解向量X=(x1, x2, …, xn)。
背包的数据结构的设计： typedef struct object {
int n;*a[i][j]; }
if(sw<=c) else
cw[i]=0;
4
cw[i]=sv;
sv=sv+wp[j].v*a[i][j];
}
在可行解中找出最优解，即找出可行解中满足目标函数的最优解。以下是找出最优解的算法：
int findmax(int x[16][4],int cv[]);/wp[k-1].wflag=1;} } if(flag==0)break; } }
然后再用贪心策略选择的算法如下：
int tx_findmaxvalue(wup wp[],int x[])return maxvalue; }5
第三章：测试结果（Testing Results）
1.蛮力法测试结果：
输入完毕后按Enter键有如下结果：
2.动态规划法调试结果
6
3.贪心法调试结果： (1).空间最优的贪心策略结果
(2).价格最优的贪心策略结果
7
(3).价格空间比最优的贪心策略结果
第四章：分析和讨论
算法的时间复杂度和空间复杂度的分析，对算法进一步改进的讨论。
附录：源代码（基于C语言的）
1.蛮力法求解01背包问题源程序： #include \"\"
8
#include \"\" #include \"\" #define N 4 #define max 10
struct product {
int id; eightmaxvalue1) } }eight+P[j].weightmaxvalue2)) } }eight+P[j].weight+P[k].weightmax)){
maxvalue3=P[i].price+P[j].price+P[k].price; kmaxa=i; kmaxb=j; kmaxc=k;
9
{ }
maxvalue2=P[i].price+P[j].price; jmaxa=i; jmaxb=j;
{
maxvalue1=P[i].price; imax=i;
}
}
}
}
eight+P[1].weight+P[2].weight+P[3].weightsystem(\"pause\"); }void scannum()d=i+1;
printf(\"\物品名称： \");
maxvalue4=P[0].price+P[1].price+P[2].price+P[3].price; printf(\"%s,%d,%d\ printf(\"%d\ printf(\"%s,%d,%d\\n\ printf(\"%d\
scanf(\"%s\ printf(\"\物品重量： \"); scanf(\"%d\ printf(\"\物品价格:\"); scanf(\"%d\
P[i].flag=0;
printf(\"\\n\"); } }
int main()入物品的信息\\n\");
10
printf(\"2.求取最佳方案\\n\"); scanf(\"%d\ switch (k) {
case 1:scannum();break;间最优\\n\"); printf(\"2.价格最优\\n\"); printf(\"3.价格空间比最优\\n\"); scanf(\"%d\ switch(Way) {
case 1:eight>wp[j+1].weight)
} break;
{ }
temp=wp[j]; wp[j]=wp[j+1]; wp[j+1]=temp;
case 2:rice>wp[j+1].price)
} break;
{ }
temp=wp[j]; wp[j]=wp[j+1]; wp[j+1]=temp;
11
case
3:rice/(float)wp[j].weight<(float)wp[j+1].price/(float)wp[j+1].weight)
} i=0;
RealWeight=wp[0].weight; TotalPrice=wp[0].price;
printf(\"被装入背包的物品是:\\n(物品名价格重量)\\n\"); while(RealWeightRealWeight-=wp[i].weight;12
printf(\"%s %d %d\\n\ i++;
RealWeight+=wp[i].weight; TotalPrice+=wp[i].price;
} break; default:
{ }
printf(\"输入错误!\\n\"); exit(1); { }
temp=wp[j]; wp[j]=wp[j+1]; wp[j+1]=temp;
TotalPrice-=wp[i].price;
printf(\"求解结束!背包所装物品总重量:%d,总
值:%d\\n\ }
void main() {
int InputWay,TotalNum,i,TotalWeight,RealWeight,Goon,TotalPrice; Project *Array; FILE *fp;
printf(\"请输入物品数量及背包容量\\n\"); scanf(\"%d%d\
if((Array=(Project*)malloc(TotalNum*sizeof(Project)))==NULL) { } else { }
Array=Input(Array,TotalNum,TotalWeight);
13
printf(\"请输入:物品名价格重量\\n\"); for(i=0;iscanf(\"%s%d%d\ printf(\"内存已满,申请空间失败!\\n\"); exit(1);printf(\"退出本次测试请按0!\\n\"); scanf(\"%d\
}while(GoBack!=0); return wp;
}
声明
我们在此声明，这个题为“蛮力法、动态查找法、贪心法求解01
背包问题”的项目的所有工作是由作为一组的我们的成员的共同的努力而完成的。尽管程序中存在很多的缺陷，需要完善。但是这是我们辛苦努力的结果。
人员安排：
程序员：刘红梅 测试员：余武丹 报告书写员：李红波
14
