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

1、算法设计与分析实验报告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 )的递归式如下： maxm( i+1, j ), m(

2、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 knapsac

3、k(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-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 =

4、 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<< "&&&&&&&&&&&&&&&&&&&&&&

5、;&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&" << endl; int traceback(int x, int w, int* m, int c, int n) /回代，求最优解 out <<

6、endl << "得到的一组最优解如下: " << endl; for(int i = 1; i < n; i+) if(mic = mi+1c)xi = 0; else xi = 1; c -= wi; xn = (mnc) ? 1:0; for(int y = 1; y <= n; y+) cout << xy << "t" cout << endl;return xn; void main() int n, c; int *m; cout << "&

7、;&&&&&&&&&&&&&&&&&&&&欢迎使用0-1背包问题程序&&&&&&&&&&&&&&&&&&&" << endl; cout << "请输入物品个数:" cin >> n ; cout << end

8、l << "请输入背包的承重："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 intn+1; m = n