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

《算法设计与分析实验报告背包问题.docx》由会员分享，可在线阅读，更多相关《算法设计与分析实验报告背包问题.docx（5页珍藏版）》请在课桌文档上搜索。

1、问题描述给定n种物品和一个背包。物品i的重量是,其价值为,背包容量为C。问应该如何选择装入背包的物品,使得装入背包中物品的总价值最大？问题分析0/1背包问题的可形式化描述为：给定C0,0,0,要求找出n元0/1向量,使得,而且达到最大。因此0/1背包问题是一个特殊的整数规划问题。算法设计设0/1背包问题的最优值为m,即背包容量是j,可选择物品为i,i+1,n时0/1背包问题的最优值。由0/1背包问题的最优子结构性质,可以建立计算m的递归式如下：maxm,m+ m=mm=0 算法实现#include #include #include int min int temp; if w temp =

2、w; else temp = c; return temp; Int max int temp; if ctemp = w; else temp = c; return temp; void knapsack/求最优值 int jmax = min; for int j = 0; j mnj = 0; for int jj = wn; jj mnjj = vn; for 1; i-/递归部分 jmax = min; forint j = 0; j mij = mi+1j; forint jj = wi; jj mijj = max; m1c = m2c; if= w1 m1c = max; c

3、out endl 最优值： m1c endl; coutendl; cout & endl; int traceback /回代,求最优解 out endl 得到的一组最优解如下: endl; forint i = 1; i ifxi = 0; else xi = 1; c -= wi; xn = ? 1:0; forint y = 1; 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 请输入每个物品的价值 : endl; forint i = 1; i cin vi; int *w = new intn+1; cout endl 请输入每个物品的重量 : endl; forint j = 1; j cin wj; int *x = new intn+1; m = new int* n+1;/动态的分配二维数组forint p = 0; p mp = new intc+1; knapsack ; traceback; 运行结果5 / 5