《算法设计与分析实验报告—背包问题》由会员分享，可在线阅读，更多相关《算法设计与分析实验报告—背包问题（6页珍藏版）》请在金锄头文库上搜索。
1、算法设计与分析实验报告0/1背包问题【问题描述】给定n种物品和一个背包。物品i的重量是w，其价值为v，背包容量为Co问应该如何选择装入背包的物品，使得装入背包中物品的总价值最大？【问题分析】0/1背包问题的可形式化描述为：给定 C0, wi 0, M 0,1 i n，要求n找出 n 元 0/1 向量(xi, X2,.,Xn),Xi 0,1 ,1 i n，使得 wx c，而且i 1nwx达到最大。因此0/1背包问题是一个特殊的整数规划问题。i 1n0 k Wn max ViXi 1rnWiXi cXi 0,1 ,1 i n【算法设计】设0/1背包问题的最优值为m( i, j )，即背包容量是j，
2、可选择物 品为i,i+1,n时0/1背包问题的最优值。由0/1背包问题的最优子结 构性质，可以建立计算 m( i, j ) 的递归式如下：Wi)+ v j Wimaxm( i+1, j ), m( i+1, j-m( i, j )=Jm(i+1,j)VnjWnm(n,j)=J00 k wn算法实现】#include #include#includeint min(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
3、 n)int jmax = min(wn-1, c);for (int j = 0; j = jmax; j+) mnj = 0;for (int jj = wn; jj 1; i-)/ 递归部分jmax = min(wi-1, c);for(int j = 0; j = jmax; j+) mij = mi+1j;for(int jj = wi; jj = w1)m1c = max(m1c, m2c-w1+v1);cout endl 最优值： m1c endl;coutendl;endl;cout &int traceback(int x, int w, int* m, int c, int
4、 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 xy t;cout endl;return xn;void main()int n, c;int *m;cout &欢&迎使用 0-1 背包问题程序 & endl;cout n ;cout endl c;int *v = new intn+1;cout endl 请输入每个物品的价值(vi): endl;for(int i = 1; i vi;int *w = new intn+1;cout endl 请输入每个物品的重量(wi): endl;for(int j = 1; j 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);【运行结果】
