算法分析与设计实验报告
第 3 次实验
姓名
学号
班级
时间
11.14下午
地点
四合院
实验名称
动态规划法求解背包问题
实验目的通过上机实验，要求掌握动态规划算法的问题描述、算法设计思想、程序设计。
利用动态规划算法求解背包问题，并计算出程序运行所需要的时间。
实验原理
给定几组数据，利用动态规划算法的思想，把 0-1 背包装满并使得其价值最大。
实验步骤
把问题分解成若干个子问题， 如背包仅可以容纳 1 个物品且可以容纳 的质量为一等。
依次求出各个子问题的最优解。
每个子问题的最优解又可以从它的子问题的最优解中得到。
通过各个子问题的最优解得到原问题的最优解。
关键代码
void KnapSack(int n,int w[],int v[],int x[],int C)
{
int i,j;
int jMax=min(w[n]-1,C);
for(j=0;j<=jMax;j++)
mV[n][j]=0;
for(j=w[n];j<=C;j++)
mV[n][j]=v[n];
for(i=n-1;i>1;i--)
{
jMax=min(w[n]-1,C);
for(j=0;j<=jMax;j++)
mV[i][j]=mV[i+1][j];
for(j=w[i];j<=C;j++)
mV[i][j]=max(mV[i+1][j],mV[i+1][j-w[i]]+v[i]);
}
mV[1][C]=mV[2][C];
if(C>=w[1])
mV[i][j]=max(mV[1][C],mV[2][C-w[1]]+v[1]);
}
void Traceback(int w[],int C,int n,int x[]){
for(int i=1;i<n;i++)
if(mV[i][C]==mV[i+1][C]) x[i]=0;
else {
x[i]=1;
C-=w[i];
}
x[n]=(mV[n][C])?1:0;
}
测试结果
实验心得
通过这次实验，我回顾了动态算法求解背包问题，在其中加入了舍伍德随机化取值过程，使数据分布更加均匀，让我熟悉了随机化算法，也让结果更加公平可靠。
本次实验在书本有详细的算法，但是刚开始的时候难以理解其精髓，后来通过和同学讨论才知道该算法与一般的做法有点不同，是从最后一个物品进行考虑的，这样方便了子问题的划分和代码的实现。这次实验让我知道，有时候不能墨守陈规，编写代码应该要打开自己的思路，从多方面进行考虑，才能写出最简单，方便的算法。
实验得分
助教签名
附录：完整代码
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
int mV[200][200]; //前i个物品装入容量为j的背包中获得的最大价值
int max(int a,int b)
{
if(a>=b)
return a;
else return b;
}
int min(int a,int b)
{
if(a<b)
return a;
else return b;
}
void KnapSack(int n,int w[],int v[],int x[],int C)
{
int i,j;
int jMax=min(w[n]-1,C);
for(j=0;j<=jMax;j++)
mV[n][j]=0;
for(j=w[n];j<=C;j++)
mV[n][j]=v[n];
for(i=n-1;i>1;i--)
{
jMax=min(w[n]-1,C);
for(j=0;j<=jMax;j++)
mV[i][j]=mV[i+1][j];
for(j=w[i];j<=C;j++)
mV[i][j]=max(mV[i+1][j],mV[i+1][j-w[i]]+v[i]);
}
mV[1][C]=mV[2][C];
if(C>=w[1])
mV[i][j]=max(mV[1][C],mV[2][C-w[1]]+v[1]);
}
void Traceback(int w[],int C,int n,int x[]){
for(int i=1;i<n;i++)
if(mV[i][C]==mV[i+1][C]) x[i]=0;
else {
x[i]=1;
C-=w[i];
}
x[n]=(mV[n][C])?1:0;
}
int main()
{
int n,i;
int C; //背包最大容量
printf("请输入背包的最大容量:\n");
scanf("%d",&C);
printf("输入物品数:\n");
scanf("%d",&n);
int w[n+1]; //物品的重量
int v[n+1]; //物品的价值
int x[n+1]; //物品的选取状态
srand(time(0));
for(i=1;i<=n;i++)
{
w[i]=rand()%35;
printf("%d\t",w[i]);
}
printf("\n");
for(i=1;i<=n;i++)
{
v[i]=rand()%20;
printf("%d\t",v[i]);
}
printf("\n");
KnapSack(n,w,v,x,C);
printf("最大物品价值为:\n");
for(i=1;i<=n;i++)
for(int j=C;j<=C;j++)
printf("%d ", mV[i][j]);
return 0;
}