实验 2 用动态规划实现0-1背包问题

实验二 用动态规划实现0-1背包问题

一．实验目的

1.熟悉动态规划法的基本原理。

2.通过本次实验加深对动态规划的理解。

二．实验内容及要求

内容：.给定n种物品和一个背包。物品i的重量是w，其价值为v，背包容量为c。问应该如何选择装入背包的物品，使得装入背包中物品的总价值最大?

要求：使用动态规划算法编程，求解0-1背包问题

三．程序列表

（1）

#include

using namespace std;

int optp[100][100];

void Knapsack(int m,int n,int w[10],int p[10])//n位物品数,m为背包的承受重量

{

for(int i=0; i<=m; i++)

{

optp[0][i]=0;

}

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

{

optp[k][0] = 0;

for(int j=1; j<= m; j++)

{

if(w[k]<=j)

{

if(p[k]+optp[k-1][j-w[k]]>optp[k-1][j])

optp[k][j]=p[k]+optp[k-1][j-w[k]];

else optp[k][j]=optp[k-1][j];

}

else

optp[k][j]=optp[k-1][j];

}

}

}

void Traceback(int m,int n,int w[10],int x[10])

{

int sum=0;

for(int k=n;k>=1;k--)

{

if(optp[k][m]==optp[k-1][m])

x[k]=0;

else

{

x[k]=1;

m=m-w[k];

sum=sum+w[k];

}

}

x[1]=optp[1][m]?1:0;

cout<<\"最大总重量:\"<}

void main()

{

int n,m;

int w[10],p[10],x[10];

cout<<\"输入物品的总个数:\";

cin>>n;

cout<<\"输入背包的总容量:\";

cin>>m;

cout<<\"依次输入物品的重量:\"<for(int i=1; i<=n; i++)

{

cin>>w[i];

}

cout<<\"依次输入物品的价值:\"<for(int k=1; k<=n;k++)

{

cin >> p[k];

}

Knapsack(m,n,w,p);

Traceback(m,n,w,x);

cout<<\"最优解为:\"<for(int l=1; l<=n;l++)

{

cout<}

cout<cout<}

四．实验结果