算法设计与分析实验报告—01背包问题.docx

算法设计与分析
实验报告
—0/1背包问题

-

【问题描述】
给定n种物品和一个背包。物品i的重量是，其价值为，背包容量为C。问应该如何选择装入背包的物品，使得装入背包中物品的总价值最大？
【问题分析】
0/1背包问题的可形式化描述为：给定C>0, >0, >0,，要求找出n元0/1向量，使得，而且达到最大。因此0/1背包问题是一个特殊的整数规划问题。

【算法设计】
设0/1背包问题的最优值为m( i, j )，即背包容量是j，可选择物品为i,i+1,…,n时0/1背包问题的最优值。由0/1背包问题的最优子结构性质，可以建立计算m( i, j )的递归式如下：

max{m( i+1, j ), m( i+1, j-)+}
m( i, j )=
m(i+1,j)

m(n,j)=
0

【算法实现】
#include <iostream.h>
#include<string.h>
#include<iomanip.h>

int min(int w, int c)
{
int temp;
if (w < c) temp = w;
else
temp = c;
return temp;
}

Int max(int w, int c)
{
int temp;
if (w > c) temp = w;
else
temp = c;
return temp;
}

void knapsack(int v[], int w[], int** m, int c, int n) //求最优值
{
int jmax = min(w[n]-1, c);

for (int j = 0; j <= jmax; j++)
m[n][j] = 0;

for (int jj = w[n]; jj <= c; jj++)
m[n][jj] = v[n];

for(int i = n-1; i > 1; i--) //递归部分
{
jmax = min(w[i]-1, c);

for(int j = 0; j <= jmax; j++)
m[i][j] = m[i+1][j];

for(int jj = w[i]; jj <= c; jj++)
m[i][jj] = max(m[i+1][jj], m[i+1][jj-w[i]]+v[i]);
}

m[1][c] = m[2][c];

if(c >= w[1])
m[1][c] = max(m[1][c], m[2][c-w[1]]+v[1]);

cout << endl << "最优值：" << m[1][c] << endl;

cout<<endl;
cout<< "&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&" << endl;
}

int traceback(int x[], int w[], int** m, int c, int n) //回代，求最优解
{
out << endl << "得到的一组最优解如下: " << endl;

for(int i = 1; i < n; i++)
{
if(m[i][c] == m[i+1][c]) x[i] = 0;
else
{
x[i] = 1;
c -= w[i];
}
}

x[n] = (m[n][c]) ? 1:0;

for(int y = 1; y <= n; y++)
cout << x[y] << "\t";

cout << endl;

return x[n];
}

void main()
{
int n, c;
int **m;

cout << "&&&&&&&&&&&&&&&&&&&&&欢迎使用0-1背包问题程序&&&&&&&&&&&&&&&&&&&" << endl;
cout << "请输入物品个数: ";
cin >> n ;
cout << endl << "请输入背包的承重：";
cin >> c;

int *v = new int[n+1];

cout << endl << "请输入每个物品的价值 (v[i]): " << endl;
for(int i = 1; i <= n; i++)
cin >> v[i];

int *w = new int[n+1];
cout << endl << "请输入每个物品的重量 (w[i]): " << endl;
for(int j = 1; j <= n; j++)
cin >> w[j];

int *x = new int[n+1];
m = new int* [n+1]; //动态的分配二维数组
for(int p = 0; p < n+1; p++)
m[p] = new int[c+1];

knapsack (v, w, m, c, n);
traceback(x, w, m, c, n);

}
【运行结果】