算法设计与分析
实验报告
—0/1背包问题
-
【问题描述】
给定n 种物品和一个背包。

物品i 的重量是i w ，其价值为i v ，背包容量为C 。

问应该如何选择装入背包的物品，使得装入背包中物品的总价值最大？
【问题分析】
0/1背包问题的可形式化描述为：给定C>0, i w >0, i v >0,1i n ≤≤，要求找出n 元0/1向量{}12(,,...,),0,1,1n i x x x x i n ∈≤≤，使得n
1i i i w x c =≤∑，而且
n
1
i i i v x =∑达到最大。

因此0/1背包问题是一个特殊的整数规划问题。

0n k w ≤≤1
max n
i i i v x =∑
n
1
i i i w x c =≤∑
{}0,1,1i x i n ∈≤≤
【算法设计】
设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-i w )+i v } i j w ≥
m( i, j )= m(i+1,j)
n v n j w >
m(n,j)=
0 0n k w ≤≤
【算法实现】
#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);
}
【运行结果】。