课程设计报告
( 2013 -- 2014 年度第 一 学期)
名 称： 算法设计与分析 题 目 0—1背包问题 院 系： 信息工程 班 级： 网络11k1 学 号： 学生姓名： 指导教师： 牛华为 设计周数： 1周
成 绩：
日期：2013年 11月 15
一、目的和要求
了解并掌握动态规划算法；
用动态规划算法解决0-1背包问题。 二、实验环境
用VC6.0软件进行编程 三、实验内容
0-1背包问题：给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为c。问应如何选择装入背包中的物品，使得装入背包中的物品的总价值最大?
在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分物品i。0-1背包问题是一个特殊的整数规划问题。 四、 问题分析
在0/1背包问题中物体或者被装入背包或者不被装入背包只有两种选择。 循环变量i、j意义：前i个物品能够装入载重量为j的背包中，数组c意义：c[i][j]表示前i个物品能装入载重量为j的背包中物品的最大价值。若w[i]>j第i个物品不装入背包 ，否则若w[i]<=j且第i个物品装入背包后的价值>c[i-1][j]，则记录当前最大价值，替换为第i个物品装入背包后的价值。 其c++部分代码如下：
#include
void knapsack(int a[100][100],int s[100],int v[100],int n,int C) { for(int i=0;i<=C;i++) { a[0][i]=0; } for( i=1;i<=n;i++) { a[i][0]=0; for(int j=1;j<=C;j++) { if(s[i]<=j) { if(v[i]+a[i-1][j-s[i]]>a[i-1][j]) a[i][j]=v[i]+a[i-1][j-s[i]]; else a[i][j]=a[i-1][j]; } else a[i][j]=a[i-1][j]; } } }
void outputsack(int a[100][100], int x[100],int s[100],int n,int C) { for(int k=n;k>=1;k--) { if(a[k][C]=a[k-1][C]) x[k]=0; else { x[k]=1; C=C-s[k]; } } x[1]=a[1][C]?1:0; }
int main() { int a[100][100]; int s[100]; int v[100]; int x[100]; int C,n; cout<<\请输入物品的总个数n:\ cin>>n; cout<<\请输入背包的总容量C:\ cin>>C; cout<<\请依次输入物品的体积s[i]:\ for(int i=1;i<=n;i++) {cin>>s[i];} cout<<\请对应输入物品的价值v[i]:\ for( i=1;i<=n;i++) {cin>>v[i];} knapsack(a,s,v,n,C); outputsack(a,x,s,C,n); //max(s,v); //for( i=1;i<=n;i++) //cout<
五、调试过程及实验结果
六、总结
01背包问题是最基本的背包问题，它包含了背包问题中设计状态、方程的最基本思想，另外，别的类型的背包问题往往也可以转换成01背包问题求解。
实验二：贪心算法解0—1背包问题
一、实验目的
学习掌贪心算法法思想。 二、实验内容
用贪心法求解0—1背包问题，并输出问题的最优解。
问题描述：给定n种物品和一背包。物品i的重量是Wi，其价值为Vi，背包的容量是c，问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大。
三、实验条件
用VC6.0软件进行编程。 四、需求分析
对于给定n种物品和一背包。在容量最大值固定的情况下，要求装入的物品价值最大化。 五、基本思想：
总是对当前的问题作最好的选择，也就是局部寻优。最后得到整体最优。总是选择单位价值最高的物品 六、代码如下：
#include
float p; //物品效益 float w; //物品重量
float X; //物品该放的数量 int flag; //物品编号 };//物品信息结构体
void Insertionsort(goodinfo goods[],int n) //插入排序，按pi/wi价值收益进行排序，一般教材上按冒泡排序 {
int j,i;
for(j=2;j<=n;j++) {
goods[0]=goods[j]; i=j-1;
while (goods[0].p>goods[i].p) {
goods[i+1]=goods[i]; i--; }
goods[i+1]=goods[0]; }
} //按物品效益，重量比值做升序排列
void bag(goodinfo goods[],float M,int n) {
float cu; int i,j;
for(i=1;i<=n;i++) goods[i].X=0; cu=M; //背包剩余容量 for(i=1;i { if(goods[i].w goods[i].X=1; cu-=goods[i].w;//确定背包新的剩余容量 } else { goods[i].X=0; } for(j=2;j<=n;j++) /*按物品编号做降序排列*/ { goods[0]=goods[j]; i=j-1; while (goods[0].flag goods[i+1]=goods[i]; i--; } goods[i+1]=goods[0];