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

算法设计与分析

实验报告

—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 #include #include

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<

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);

}