注意：红色的部分需要用自己的代码或内容进行替换。
湖南涉外经济学院
实 验 报 告
实验课程： 算法设计与分析
实验项目： 动态规划法解0-1背包问题
姓名 班级 学号
学院 专业
实验地点 分组组号
实验时间 年 月 日 星期 一 第 12 节
指导老师
【实验目的和要求】
1. 理解动态规划算法的原理和基本要素；
2．要求用动态规划法求解0-1背包问题；
3．要求交互输入背包容量，物品重量数组，物品价值数组；
4. 要求显示结果。
【系统环境】
操作系统：Windows XP 操作系统
开发工具：VC++6.0英文企业版
开发语言：C，C++
【实验原理】
1、问题描述
给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的所能够容纳的重量为c。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大？
在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入物品i的一部分。
2、实验原理
0-1背包问题具有最优子结构性质，可以据此定义递归关系，建立递归方程，并以自底向上的方式计算最优值，根据计算最优值时的得到的信息，构造最优解。
设所给0-1背包问题的子问题的最优值m(i,j)，即m(i,j)是背包重量为j，可选物品为i，i+1，…，n-1时的最优值。由最优子结构性质，可以计算出m(i,j)的递归式如下：
【实验任务与步骤】
1、实验步骤
(1) 完成函数Knapsack，得到子问题的最优值数组。
(2) 完成函数Traceback，根据最优值构造最优解。
(3) 编写主函数，调用Knapsack和Traceback和进行测试，并进行输出。
2、源程序代码
// 此处为解决问题的完整源程序，要求带注释，代码必须符合书写规范。
……
【实验结论(包括实验数据处理、问题与解决办法、心得体会、意见与建议等)】
// 此处为程序运行的结果，要求有程序运行输入输出实例，要求至少有两组实验结果。
// 必须写心得体会、意见与建议等，或者遇到的问题、难题等。
……
可使用下列测试数据：
有7个物品，重量分别为2，3，5，7，1，4，1，效益分别为10，5，15，7，6，18，3，背包的容量为15，输出背包的最大效益，背包剩余的容量，放入背包中的物品为。
第二篇：0-1背包问题-贪心法和动态规划法求解
实验四 “0-1”背包问题
一、 实验目的与要求
熟悉C/C++语言的集成开发环境；
通过本实验加深对贪心算法、动态规划算法的理解。
二、 实验内容:
掌握贪心算法、动态规划算法的概念和基本思想，分析并掌握“0-1”背包问题的求解方法，并分析其优缺点。
三、 实验题
1. “0-1”背包问题的贪心算法
2. “0-1”背包问题的动态规划算法
说明：背包实例采用教材P132习题六的6-1中的描述。要求每种的算法都给出最大收益和最优解。
设有背包问题实例n=7，M=15,，(w0,w1,。。。w6)=（2,3,5,7,1,4,1），物品装入背包的收益为：（p0，p1，。。。，p6）=（10,5,15,7,6,18,3）。求这一实例的最优解和最大收益。
四、 实验步骤
理解算法思想和问题要求；
编程实现题目要求；
上机输入和调试自己所编的程序；
验证分析实验结果；
整理出实验报告。
五、 实验程序
// 贪心法求解
#include<iostream>
#include"iomanip"
using namespace std;
//按照单位物品收益排序，传入参数单位物品收益，物品收益和物品重量的数组，运用冒泡排序
void AvgBenefitsSort(float *arry_avgp,float *arry_p,float *arry_w ); //获取最优解方法，传入参数为物品收益数组，物品重量数组，最后装载物品最优解的数组和还可以装载物品的重量
float GetBestBenifit(float *arry_p,float *arry_w,float *arry_x,float u);
int main(){
float w[7]={2,3,5,7,1,4,1}; //物品重量数组
float p[7]={10,5,15,7,6,18,3}; //物品收益数组
float avgp[7]={0}; //单位毒品的收益数组
float x[7]={0}; //最后装载物品的最优解数组 const float M=15; //背包所能的载重
float ben=0; //最后的收益
AvgBenefitsSort(avgp,p,w);
ben=GetBestBenifit(p,w,x,M);
cout<<endl<<ben<<endl; //输出最后的收益
system("pause");
return 0;
}
//按照单位物品收益排序，传入参数单位物品收益，物品收益和物品重量的数组，运用冒泡排序
void AvgBenefitsSort(float *arry_avgp,float *arry_p,float *arry_w ) {
//求出物品的单位收益
for(int i=0;i<7;i++)
{
arry_avgp[i]=arry_p[i]/arry_w[i];
}
cout<<endl;
//把求出的单位收益排序，冒泡排序法
int exchange=7;
int bound=0;
float temp=0;
while(exchange)
{
bound=exchange;
exchange=0;
for(int i=0;i<bound;i++)
{
if(arry_avgp[i]<arry_avgp[i+1])
{
//交换单位收益数组
temp=arry_avgp[i];
arry_avgp[i]=arry_avgp[i+1];
arry_avgp[i+1]=temp;
//交换收益数组
temp=arry_p[i];
arry_p[i]=arry_p[i+1];
arry_p[i+1]=temp;
//交换重量数组
temp=arry_w[i];
arry_w[i]=arry_w[i+1];
arry_w[i+1]=temp;
exchange=i;
}
}
}
}
//获取最优解方法，传入参数为物品收益数组，物品重量数组，最后装载物品最
优解的数组和还可以装载物品的重量
float GetBestBenifit(float *arry_p,float *arry_w,float *arry_x,float u)
{
int i=0; //循环变量i
float benifit=0; //最后收益
while(i<7)
{
if(u-arry_w[i]>0)
{
arry_x[i]=arry_w[i]; //把当前物品重量缴入最优解数组
benifit+=arry_p[i]; //收益增加当前物品收益 u-=arry_w[i]; //背包还能载重量减去当前物品重量
cout<<arry_x[i]<<" "; //输出最优解
}
i++;
}
return benifit; //返回最后收益
}
//动态规划法求解
#include<stdio.h>
#include<math.h>
#define n 6
void DKNAP(int p[],int w[],int M,const int m); void main()
{
int p[n+1],w[n+1];
int M,i,j;
int m=1;
for(i=1;i<=n;i++)
{
m=m*2;
printf("\nin put the weight and the p:"); scanf("%d %d",&w[i],&p[i]);
}
printf("%d",m);
printf("\n in put the max weight M:"); scanf("%d",&M);
DKNAP(p,w,M,m);
}
void DKNAP(int p[],int w[],int M,const int m) {
int p2[m],w2[m],pp,ww,px;
int F[n+1],pk,q,k,l,h,u,i,j,next,max,s[n+1]; F[0]=1;
p2[1]=w2[1]=0;
l=h=1;
F[1]=next=2;
for(i=1;i<n;i++)
{
k=l;
max=0;
u=l;
for(q=l;q<=h;q++)
if((w2[q]+w[i]<=M)&&max<=w2[q]+w[i]) {
u=q;
max=w2[q]+w[i];
}
for(j=l;j<=u;j++)
{
pp=p2[j]+p[i];
ww=w2[j]+w[i];
while(k<=h&&w2[k]<ww) { p2[next]=p2[k]; w2[next]=w2[k]; next++; k++; } if(k<=h&&w2[k]==ww) { if(pp<=p2[k]) pp=p2[k]; k++; } else if(pp>p2[next-1]) { p2[next]=pp; w2[next]=ww;next++; } while(k<=h&&p2[k]<=p2[next-1]) k++; } while(k<=h) { p2[next]=p2[k]; w2[next]=w2[k]; next=next+1; k++; } l=h+1; h=next-1; F[i+1]=next; } for(i=1;i<next;i++) printf("%2d%2d ",p2[i],w2[i]); for(i=n;i>0;i--) { next=F[i]; next--; pp=pk=p2[next]; ww=w2[next]; while(ww+w[i]>M&&next>F[i-1]) { next=next-1; pp=p2[next];
} ww=w2[next]; } if(ww+w[i]<=M&&next>F[i-1]) px=pp+p[i]; if(px>pk&&ww+w[i]<=M) { s[i]=1; M=M-w[i]; printf("M=%d ",M); } else s[i]=0; } for(i=1;i<=n;i++) printf("%2d ",s[i]);
实验结果 六、
1、贪心法截图：
七、
实验分析