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

1、算法设计与分析实验报告0/1背包问题【问题描述】给定n种物品和一个背包。物品i的重量是Wi ,其价值为Vi ,背包容量为C问应该如何选择装入背包的物品，使得装入背包中物品的总价值最大？【问题分析】0/1背包问题的可形式化描述为：给定C>0, w >0, M >0,1 G兰n，要求n找出 n 元 0/1 向量(x-i,x2,.,xn),xi 0,1, 1 <n，使得瓦WjXj兰c，而且i=1n工MX达到最大。因此0/1背包问题是一个特殊的整数规划问题。i 4n0 乞 k 乞 Wn max 二 v)xiAr nZ WjXi =1X '0,1,1 乞 i 乞 n【算法

2、设计】设0/1背包问题的最优值为m( i, j),即背包容量是j,可选择物品为i,i+1,n时0/1背包问题的最优值。由0/1背包问题的最优子结构性质，可以建立计算m( i, j )的递归式如下:maxm( i+1, j ), m( i+1, j- Wi)+ Vi j _ Wim( i, j )=m(i+1,j)k Vnj >WnYm(n,j)= I00三k三Wn【算法实现】#include <iostream.h>#include<string.h>#include<iomanip.h>int min(int w, int c)int temp;if

3、 (w < c) temp = w;elsetemp = c;return temp;Int max(int w, int c)int temp;if (w > c) temp = w;elsetemp = c;return temp;/求最优值void knapsack(int v, int w, int* m, int c, int n)int jmax = min(wn-1, c);for (int j = 0; j <= jmax; j+)mnj = 0;for (int jj = wn; jj <= c; jj+)mnjj = vn;for(int i = n

4、-1; i > 1; i-)/ 递归部分jmax = min(wi-1, c);for(int j = 0; j <= jmax; j+)mij = mi+1j;for(int jj = wi; jj <= c; jj+)mijj = max(mi+1jj, mi+1jj-wi+vi);m1c = m2c;if(c >= w1)m1c = max(m1c, m2c-w1+v1);cout << endl << " 最优值： " << m1c << endl;cout<<endl;cout&l

5、t;<"&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&am

6、p;&&&& &" << endl;int traceback(int x, int w, int* m, int c, int n) / 回代，求最优解out << endl << " 得到的一组最优解如下 : " << endl;for(int i = 1; i < n; i+)if(mic = mi+1c) xi = 0;elsexi = 1;c -= wi;xn = (mnc) ? 1:0;for(int y = 1; y <= n; y+) cout &l

7、t;< xy << "t"cout << endl;return xn;void main()int n, c;int *m;cout << "&&&&&&&&&&&&&&&&&&&&& 欢 迎 使 用 0-1 背 包 问 题 程 序 &&&&&&&&&&&&&a

8、mp;&&&&&&" << endl;cout << " 请输入物品个数 : "cin >> n ;cout << endl << " 请输入背包的承重： "cin >> c;int *v = new intn+1;cout << endl << " 请输入每个物品的价值 (vi): " << endl;for(int i = 1; i <= n; i+)cin >> vi;int *w = new intn+1;cout << endl << " 请输入每个物品的重量 (wi): " << endl;for(int j = 1; j <= n; j+)cin >> wj;int *x = new int