算法设计 0-1背包问题用动态规划的递归实现与非递归实现

华南农业大学

《算法分析与设计》

课程实验

专业年级：10信息与计算科学2班

学生学号： 22号

学生姓名： 梁高鼎

实验题目：用动态规划法求解0-1背包问题

指导老师： 梁 茹 冰

实验时间： 2012年11月5日

一、实验内容

用动态规划法求解0-1背包问题

要求：(1)用递归实现（备忘录方法）

(2)用非递归实现（动态规划法）

二、实验步骤

2.1、理解算法思想和问题要求；

2.2、写出每个操作的算法 2.2.1 递归实现（备忘录方法）

void find(int i,float tw,float tv)

{

int k;

//物品i包含在当前方案的可能性

if(tw+a[i].weight <= limitW)

{

cop[i]=1;

if(i<n-1)

find(i+1,tw+a[i].weight,tv);

else

{

for(k=0;k<n;++k)

option[k]=cop[k];

maxv=tv;

}

}

cop[i]=0;

//物品i不包含在当前方案的可能性

if(tv-a[i].value>maxv)

{

if(i<n-1)

find(i+1,tw,tv-a[i].value);

else{

for(k=0;k<n;++k)

option[k]=cop[k];

maxv=tv-a[i].value;

}

}

}

2.2.2 非递归实现（动态规划法）

int knapsack(int &n,int &C,int s[M],int p[M],int V[M][M])

{

int i,j;

for (i=0;i<=n;i++)

for(j=0;j<=C;j++)

{

if(i==0||j==0)

V[i][j]=0;

else if(s[i]>j)

V[i][j]=V[i-1][j];

else if(s[i]<=j)

V[i][j]=max(V[i-1][j],V[i-1][j-s[i]]+p[i]);

}

return

V[n][C];

};

void traceback(int n,int C,int s[M],int x[M],int V[M][M])

{

for(int i=1;i<=n;i++)

{

if(V[i][C]==V[i-1][C])

x[i]=0;

else

{

x[i]=1;

C=C-s[i];

}

}

}

2.3、编程实现题目要求；

2.4、调试程序；

2.5、实验数据及实验结果；

2.5.1 递归方法：

输入数据：背包容量为50公斤。物品1重10公斤，价值60元；物品2重20公斤，价值100元；物品3重30公斤，价值120元。

输出结果：

2.5.2 非递归方法：

输入数据：背包容量为50公斤。物品1重10公斤，价值60元；物品2重20公斤，价值100元；物品3重30公斤，价值120元。

输出结果：

2.6、算法时间复杂度

2.6.1 递归方法：O(n3)

2.6.2 非递归方法：O(n3)

三、总结

通过本次实验，让我意识到我对编程的不足,但也了解到自己的成长空间还很大。

附录：源代码

(1) 递归实现：

#include <stdio.h>

#define N 100 //最大物品总种数

int n;//物品总种数

float limitW;//限制的总重量

float totV;//全部物品的总价值

float maxv;//解的总价值

int option[N];//解的选择

int cop[N];//当前解的选择

struct {//物品结构

float weight;

float value;

}a[N];

void find(int i,float tw,float tv)

{

int k;

//物品i包含在当前方案的可能性

if(tw+a[i].weight <= limitW)

{

cop[i]=1;

if(i<n-1)

find(i+1,tw+a[i].weight,tv);

else

{

for(k=0;k<n;++k)

option[k]=cop[k];

maxv=tv;

}

}

cop[i]=0;

//物品i不包含在当前方案的可能性

if(tv-a[i].value>maxv)

{

if(i<n-1)

find(i+1,tw,tv-a[i].value);

else{

for(k=0;k<n;++k)

option[k]=cop[k];

maxv=tv-a[i].value;

}

}

}

int main()

{

int k;

float w,v;

printf("输入物品种数:");

scanf("%d",&n);

printf("输入各物品的重量:");

for(k=0;k<n;++k){

scanf("%f",&w);

a[k].weight = w;

}

printf("输入各物品的价值:");

for(totV=0.0,k=0;k<n;++k){

scanf("%f",&v);

a[k].value = v;

totV += v;

}

printf("输入限制重量:");

scanf("%f",&limitW);

maxv=0.0;

for(k=0;k<n;++k)cop[k]=0;

find(0,0.0,totV);

printf("选择的物品:");

for(k=0;k<n;++k)

printf("%d",option[k]);

printf("\n总价值为: %f",maxv);

getchar();

getchar() ;

return 0;

}

(2)非递归实现：

#include<iostream>

using namespace std;

#define max(a,b) a>b?a:b

#define M 100

void display(int &n,int &C,int s[M],int p[M])

{

int i;

cout<<"please input n:";

cin>>n;

cout<<endl;

cout<<"please input tw:";

cin>>C;

cout<<endl;

cout<<"please input w:"<<endl;

s[0]=0;

for(i=1;i<=n;i++)

cin>>s[i];

cout<<"please input v"<<endl;

p[0]=0;

for(i=1;i<=n;i++)

cin>>p[i];

};

int knapsack(int &n,int &C,int s[M],int p[M],int V[M][M])

{

int i,j;

for (i=0;i<=n;i++)

for(j=0;j<=C;j++)

{

if(i==0||j==0)

V[i][j]=0;

else if(s[i]>j)

V[i][j]=V[i-1][j];

else if(s[i]<=j)

V[i][j]=max(V[i-1][j],V[i-1][j-s[i]]+p[i]);

}

return V[n][C];

};

void traceback(int n,int C,int s[M],int x[M],int V[M][M])

{

for(int i=1;i<=n;i++)

{

if(V[i][C]==V[i-1][C])

x[i]=0;

else

{

x[i]=1;

C=C-s[i];

}

}

};

void main()

{

int i,j,n,C;

char ch;

int s[M],p[M],x[M];

int V[M][M];

while(1)

{

display(n,C,s,p);

cout<<"运算结果如下："<<endl;

for(i=1;i<=n;i++)

x[i]=0;

knapsack(n,C,s,p,V);

cout<<" ";

for(j=0;j<=C;j++)

cout<<j<<" ";

cout<<endl;

for(i=0;i<=n;i++)

{

cout<<i<<" ";

for(j=0;j<=C;j++)

{

cout<<V[i][j]<<" ";

}

cout<<endl;

cout<<endl;