《蛮力法、动态规划法、回溯法和分支限界法求解01背包问题.doc》由会员分享，可在线阅读，更多相关《蛮力法、动态规划法、回溯法和分支限界法求解01背包问题.doc（12页珍藏版）》请在金锄头文库上搜索。
1、一、实验内容：分别用蛮力法、动态规划法、回溯法和分支限界法求解0/1背包问题。注：0/1背包问题：给定种物品和一个容量为的背包，物品的重量是，其价值为，背包问题是如何使选择装入背包内的物品，使得装入背包中的物品的总价值最大。其中，每种物品只有全部装入背包或不装入背包两种选择。二、所用算法的基本思想及复杂度分析：1.蛮力法求解0/1背包问题：1）基本思想：对于有n种可选物品的0/1背包问题，其解空间由长度为n的0-1向量组成,可用子集数表示。在搜索解空间树时，深度优先遍历，搜索每一个结点，无论是否可能产生最优解，都遍历至叶子结点，记录每次得到的装入总价值，然后记录遍历过的最大价值。2）代码:#i
2、nclude#includeusing namespace std;#define N 100/最多可能物体数struct goods/物品结构体int sign;/物品序号int w;/物品重量int p;/物品价值aN;bool m(goods a,goods b)return (a.p/a.w)(b.p/b.w);int max(int a,int b)return an-1)if(bestPcp&cw+ai.w=C)for (int k=0;kn;k+)Xk=cxk;/存储最优路径bestP=cp;return bestP;cw=cw+ai.w;cp=cp+ai.p;cxi=1;/装入
3、背包Force(i+1);cw=cw-ai.w;cp=cp-ai.p;cxi=0;/不装入背包Force(i+1);return bestP;int KnapSack1(int n,goods a,int C,int x)Force(0);return bestP;int main()goods bN;printf(物品种数n: );scanf(%d,&n);/输入物品种数printf(背包容量C: );scanf(%d,&C);/输入背包容量for (int i=0;in;i+)/输入物品i的重量w及其价值vprintf(物品%d的重量w%d及其价值v%d: ,i+1,i+1,i+1);sc
4、anf(%d%d,&ai.w,&ai.p);bi=ai;int sum1=KnapSack1(n,a,C,X);/调用蛮力法求0/1背包问题printf(蛮力法求解0/1背包问题:nX= );for(i=0;in;i+)coutXi ;/输出所求Xn矩阵printf(装入总价值%dn,sum1);bestP=0,cp=0,cw=0;/恢复初始化3）复杂度分析：蛮力法求解0/1背包问题的时间复杂度为：。2.动态规划法求解0/1背包问题：1）基本思想：令表示在前个物品中能够装入容量为的背包中的物品的最大值，则可以得到如下动态函数：按照下述方法来划分阶段：第一阶段，只装入前1个物品，确定在各种情况下
5、的背包能够得到的最大价值；第二阶段，只装入前2个物品，确定在各种情况下的背包能够得到的最大价值；以此类推，直到第个阶段。最后，便是在容量为的背包中装入个物品时取得的最大价值。 2）代码： #include #include using namespace std; #define N 100/最多可能物体数 struct goods/物品结构体 int sign;/物品序号 int w;/物品重量 int p;/物品价值 aN; bool m(goods a,goods b) return (a.p/a.w)(b.p/b.w); int max(int a,int b) return ab?b
6、:a; int n,C,bestP=0,cp=0,cw=0; int XN,cxN; int KnapSack2(int n,goods a,int C,int x) int VN10*N; for(int i=0;i=n;i+)/初始化第0列 Vi0=0; for(int j=0;j=C;j+)/初始化第0行 V0j=0; for(i=1;i=n;i+)/计算第i行，进行第i次迭代 for(j=1;j=C;j+) if(j0;i-) if (VijVi-1j) xi-1=1; j=j-ai-1.w; elsexi-1=0; return VnC;/返回背包取得的最大价值 int main()
7、 goods bN; printf(物品种数n: ); scanf(%d,&n);/输入物品种数 printf(背包容量C: ); scanf(%d,&C);/输入背包容量 for (int i=0;in;i+)/输入物品i的重量w及其价值v printf(物品%d的重量w%d及其价值v%d: ,i+1,i+1,i+1); scanf(%d%d,&ai.w,&ai.p); bi=ai; int sum2=KnapSack2(n,a,C,X);/调用动态规划法求0/1背包问题 printf(动态规划法求解0/1背包问题:nX= ); for(i=0;in;i+) coutXi ;/输出所求Xn矩
8、阵 printf(装入总价值%dn,sum2); for (i=0;in;i+) ai=bi; /恢复aN顺序 3）复杂度分析:动态规划法求解0/1背包问题的时间复杂度为：。3.回溯法求解0/1背包问题：1）基本思想：回溯法：为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数(bounding function)来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。这种具有限界函数的深度优先生成法称为回溯法。对于有n种可选物品的0/1背包问题，其解空间由长度为n的0-1向量组成,可用子集数表示。在搜索解空间树时，只要其左儿子结点是一个可行结点，搜索就进入左子树。当右子树中
9、有可能包含最优解时就进入右子树搜索。 2）代码: #include #include using namespace std; #define N 100/最多可能物体数 struct goods/物品结构体 int sign;/物品序号 int w;/物品重量 int p;/物品价值 aN; bool m(goods a,goods b) return (a.p/a.w)(b.p/b.w); int max(int a,int b) return an-1) if(bestPcp) for (int k=0;kn;k+)Xk=cxk;/存储最优路径 bestP=cp; return best
10、P; if(cw+ai.w=C)/进入左子树 cw=cw+ai.w; cp=cp+ai.p; cxai.sign=1;/装入背包 BackTrack(i+1); cw=cw-ai.w; cp=cp-ai.p;/回溯，进入右子树 cxai.sign=0;/不装入背包 BackTrack(i+1); return bestP; int KnapSack3(int n,goods a,int C,int x) for(int i=0;in;i+) xi=0; ai.sign=i; sort(a,a+n,m);/将各物品按单位重量价值降序排列 BackTrack(0); return bestP; int main() goods bN; printf(物品种数n: ); scanf(%d,&n);/输入物品种数 printf(背包容量C: );
