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

问题描述给定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<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<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 = 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<< "&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&" << 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; 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 << "&&&&&&&&&&&&&&&&&&&&&欢迎使用0-1背包问题程序&&&&&&&&&&&&&&&&&&&" << 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 intn+1; m = new int* n+1;/动态的分配二维数组for<int p = 0; p < n+1; p+> mp = new intc+1; knapsack <v, w, m, c, n> traceback<x, w, m, c, n> 运行结果5 / 5