当前位置:首页 >> 计算机软件及应用 >>

动态规划和回溯法解0-1背包问题

0-1 背包问题

一、问题描述与分析
经常遇到一些复杂的问题, 有时我们将待求解问题分解成若干个子问题, 先求解子问题, 然后从这些子问题的解得到原问题的解。 由于分解到的子问题往往不是独立的, 用一个表来 记录所有已解决的子问题的答案, 这样就得到了原问题的解, 这就是动态规划法的基本思想。 回溯法有“通用解题法”之称。它可以系统地搜索问题的所有解。回溯法的基本做法是 搜索,或是一种组织得井井有条的,能避免不必要搜索的穷举式搜索法。这种方法适用于解 一些组合数相当大的问题。回溯法在问题的解空间树中,按深度优先策略,从根结点出发搜 索解空间树。算法搜索至解空间树的任意一点时,先判断该结点是否包含问题的解。如果肯 定不包含, 则跳过对该结点为根的子树的搜索, 逐层向其祖先结点回溯; 否则, 进入该子树, 继续按深度优先策略搜索。这种以深度优先方式搜索问题解的算法称为回溯法。 0-1 背包问题:给定 n 种物品和一背包。物品 i 的重量是 wi,其价值为 vi,背包的容量 为 C。问:应该如何选择装入背包的物品,使得装入背包中物品的总价值最大?

二、算法设计
1. 设所给 0-1 背包问题的子问题 max

?
k ?i

n

vk xk

? ? wk xk ? j ? k ?i 和?x 的最有值为 m(i,j)的背包容量为 k ??0 ,1?,i ? k ? n ? ?
n

j, 可选择物品为 i,i+1,...,n 时 0-1 背包问题的最优值。 由 0-1 背包问题的最优子结构性质, 可以建立如下计算 m(i,j)的递归式:

m?i, j? ?

? ? ? ?? ?

max m i ?1, j ?,m?i ?1, j ?wi ??vi ? j ?wi m i ?1, j --0? j ?wi vn ?? j ?wn 0??0? j ?wn

m?n, j ? ?
2.

此方法为动态规划解 0-1 背包问题。 0-1 背包问题是子集选取问题。一般情况下,0-1 背包问题是 NP 难的。0-1 背包问题的 解空间可用子集树表示。解 0-1 背包问题的回溯法与装载问题的回溯法十分相似。在搜 索解空间树时,只要其左儿子结点是一个可行结点,搜索就进入其左子树。当右子树有 可能最优解时才进入右子树搜索;否则将右子树剪去。设 r 是当前剩余物品价值总和; cp 是当前价值;bestp 是当前最优价值。当 cp+r≤bestp 时,可剪去右子树。计算右子树 中解的上界的更好方法是将剩余物品依其单位重量价值排序, 然后依次装入物品, 直至 装不下时,再装入该物品的一部分而装满背包,由此得到的价值是右子树中解的上界。 此方法为回溯法解 0-1 背包问题。

三、得出算法:
1. 动态规划解 0-1 背包算法: Void KnapSack(int n,int w[],int v[],int x[],int C) { int i,j; for(i=0;i<=n;i++) V[i][0]=0;

for(j=0;j<=C;j++) V[0][j]=0; for(i=0;i<=n-1;i++) for(j=0;j<=C;j++) if(j<w[i]) V[i][j]=V[i-1][j]; else V[i][j]=max(V[i-1][j],V[i-1][j-w[i]]+v[i]); } Void trace(int n,int w[],int v[],int x[],int C) { for(i=n-1;i>=0;i--) { if(V[i][j]>V[i-1][j]) { x[i]=1; j=j-w[i]; } else x[i]=0; } printf("状态为:\n"); for(i=0;i<n;i++) printf("%d ",x[i]); printf("\n"); return V[n-1][C]; } 2.回溯法解 0-1 背包: public static double bound(int i){ //就算上界 int cleft=c-cw; double bound=cp; //以物品单位重量加之递减顺序装入物品 while(i<=n&&w[i]<=cleft) { cleft-=w[i]; bound+=p[i]; i++; } //装满背包 if(i<=n) bound+=(double)p[i]*cleft/w[i]; return bound; } 递归回溯寻找最优解: public static void backtrack(int i){ if(i>n) //到达叶结点

{ bestp=cp; return; } //搜索子树 if(cw+w[i]<=c) {//进入左子树 cw+=w[i]; cp+=p[i]; backtrack(i+1); cw-=w[i]; cp-=p[i]; } if(bound(i+1)>bestp) backtrack(i+1); //进入右子树 } 3.

四、算法实现
1) 动态规划解 0-1 背包: #include <stdio.h> int V[50][50]; int max(int a,int b) { if(a>b) return a; else return b; }

int KnapSack(int n,int w[],int v[],int x[],int C) {

int i,j; for(i=0;i<=n;i++) V[i][0]=0; for(j=0;j<=C;j++) V[0][j]=0; for(i=0;i<=n-1;i++) for(j=0;j<=C;j++) if(j<w[i]) V[i][j]=V[i-1][j]; else V[i][j]=max(V[i-1][j],V[i-1][j-w[i]]+v[i]); j=C; for(i=n-1;i>=0;i--) { if(V[i][j]>V[i-1][j]) { x[i]=1; j=j-w[i]; } else x[i]=0; }

printf("状态为:\n"); for(i=0;i<n;i++) printf("%d ",x[i]); printf("\n"); return V[n-1][C];

}

void main() { int s,C,i,n,w[20],v[20],x[20]; printf("输入背包的容量和物品数量:\n"); scanf("%d %d",&C,&n); printf("分别输入物品的价值和重量:\n"); for(i=0;i<n;i++) scanf("%d %d",&v[i],&w[i]); s=KnapSack(n,w,v,x,C); printf("最大物品价值:"); printf("%d\n",s);

}

2) 回溯法解 0-1 背包: #include<iostream> using namespace std; class Knap { friend int Knapsack(int p[],int w[],int c,int n ); public: void print() { for(int m=1;m<=n;m++) { cout<<bestx[m]<<" "; } cout<<endl; }; private: int Bound(int i); void Backtrack(int i); int c,n,*w,*p,cw,cp,bestp,*bestx,*x; }; int Knap::Bound(int i) {

int cleft=c-cw; int b=cp; while(i<=n&&w[i]<=cleft) { cleft-=w[i]; b+=p[i]; i++; } if(i<=n) b+=p[i]/w[i]*cleft; return b; } void Knap::Backtrack(int i) { if(i>n) { if(bestp<cp) {

for(int j=1;j<=n;j++) bestx[j]=x[j]; bestp=cp; } return; } if(cw+w[i]<=c) { x[i]=1; cw+=w[i]; cp+=p[i]; Backtrack(i+1); cw-=w[i]; cp-=p[i]; } if(Bound(i+1)>bestp) { x[i]=0; Backtrack(i+1); } } class Object { friend int Knapsack(int p[],int w[],int c,int n); public: int operator<=(Object a)const { return (d>=a.d); } private: int ID; float d; }; int Knapsack(int p[],int w[],int c,int n) { int W=0; int P=0; int i=1; Object *Q=new Object[n]; for(i=1;i<=n;i++) { Q[i-1].ID=i; Q[i-1].d=1.0*p[i]/w[i]; P+=p[i];

W+=w[i]; } if(W<=c) return P; float f; for( i=0;i<n;i++) for(int j=i;j<n;j++) { if(Q[i].d<Q[j].d) { f=Q[i].d; Q[i].d=Q[j].d; Q[j].d=f; } } Knap K; K.p = new int[n+1]; K.w = new int[n+1]; K.x = new int[n+1]; K.bestx = new int[n+1]; K.x[0]=0; K.bestx[0]=0; for( i=1;i<=n;i++) { K.p[i]=p[Q[i-1].ID]; K.w[i]=w[Q[i-1].ID]; } K.cp=0; K.cw=0; K.c=c; K.n=n; K.bestp=0; K.Backtrack(1); K.print(); delete [] Q; delete [] K.w; delete [] K.p; return K.bestp; } void main() { int *p; int *w; int c=0;

int n=0; int i=0; cout<<"请输入背包容量:"<<endl; cin>>c; cout<<"输入背包数量:"<<endl; cin>>n; p=new int[n+1]; w=new int[n+1]; p[0]=0; w[0]=0; cout<<"请输入个背包的重量:"<<endl; for(i=1;i<=n;i++) cin>>w[i]; cout<<"请输入个背包的价值:"<<endl; for(i=1;i<=n;i++) cin>>p[i]; cout<<Knapsack(p,w,c,n)<<endl; }

五、结果及其分析
动态规划解 0-1 背包运行结果:

从计算 m(i,j)的递归式容易看出,上述算法 knapsack 需要 O(nc)计算时间,而算法 traceback 需要 O(n)计算时间。可以看出算法 knapasack 有两个明显的缺点,可以优化。 回溯法解 0-1 背包运行结果:

计算上界需要 O(n)时间,在最坏情况下 O( 2 )个右儿子结点需要计算上界,故解 0-1 背包问 题的回溯算法 backtrack 所需要的时间为 O(n 2 )。
n

n


相关文章:
动态规划与回溯法解决0-1背包问题.doc
动态规划与回溯法解决0-1背包问题 - 0-1 背包动态规划解决问题 一、问题描
用动态规划法与回溯法实现0-1背包问题的比较_论文.pdf
动态规划与回溯法实现0-1背包问题的比较 - 0-1背包问题是运筹学中的著名问题。也是计算机算法中的一个经典问题。本文采用动态规划和回溯法对该问题进行求解...
0-1背包问题的解决(回溯法).doc
回溯法| 背包| 0-1背包问题的解决(回溯法)_解决方案_计划/解决方案_实用文档。算法设计分析,通过回溯法动态规划的方法解决0-1背包问题。 前面...
动态规划解决算法0-1背包问题实验报告(含源代码).doc
2.掌握动态规划、贪心算法、回溯法、分支限界法的原理,并能够按其原理 编程实现...因此,,这说明是所给的 0-1 背包问题比更优的解,从而与假设矛盾。 按照上面...
回溯法求0-1背包问题.doc
回溯法求0-1背包问题 - 《算法设计分析》实验报告 学日号: 期: 姓得名: 分: 一、实验内容: 用回溯法求解 0/1 背包问题 注:给定 n 种物品一个容量...
最新动态规划解决算法0-1背包问题实验报告(含源代码).doc
实验目的及实验环境 1.使用动态规划和回溯法生成两个长字符串的最优化比对...因此,,这说明是所给的 0-1 背包问题比更优的解,从而与假设矛盾。 按照上面...
0_1背包问题的多种解法.doc
回溯法求解 0-1 背包问题的过程 递归法:在利用递归法解决 0-1 背包问题时...由此导出了许多相互重叠的子问题,所以,0-1 背包问题可以用动态规划法得到最优...
解0-1背包问题的动态规划算法.doc
解0-1背包问题动态规划算法 - 本文通过研究动态规划原理,提出了根据该原理解
算法分析与程序设计动态规划及回溯法解01背包问题.doc
算法分析与程序设计动态规划及回溯法解01背包问题 - 动态规划法、回溯法解 0-1 背包问题 2012 级 计科 庞佳奇 一、 1. 问题描述与分析 动态规划算法通常用于...
0-1背包问题求解方法综述.doc
算法分析与设计大作业 实验题目:0-1 背包问题求解方法综述 组班员: 级: 指导...目前,解决 0-1 背包 问题的方法有很多,主要有动态规划法、回溯法、分支限界法...
实验报告--动态规划法解0-1背包问题.doc
实验报告--动态规划法解0-1背包问题 - 注意:红色的部分需要用自己的代码或内
动态规划求解0-1背包问题 - 百度文库.doc
与计算科学 1 基于 MATLAB 的 0-1 背包问题动态规划求解 动态规划算法求解 ...有多种方法可以处理 它,比如分支限界法、回溯法、贪心算法等等都可以对其进行...
算法:动态规划解决0-1背包问题.doc
算法:动态规划解决0-1背包问题_计算机软件及应用_IT/计算机_专业资料。算法:...动态规划和回溯法解0-1背... 10页 1下载券 0-1背包问题-贪心法和动....
解0-1背包问题的算法比较.pdf
由于 0-1 背包的解空间树是一棵子集树, 而所要求的解要有最优解性 质,故 0-1 背包问题满足动态规划回溯法和分支限界法的求解条件。 1.2 问题描述 ...
动态规划解0-1背包问题.doc
动态规划解0-1背包问题 - 算法分析设计 实验报告 班级: 学号: 姓名: 0209404 班 020940410 杨洲 2011-11-7 上机时间: 一、实验目的要求: 1...
0-1背包问题动态规划详解及代码.doc
0/1 背包问题动态规划详解及 C 代码 背包问题动态规划详 动态规划动态规划是用...动态规划和回溯法解0-1背... 10页 1下载券 喜欢此文档的还喜欢 0...
动态规划解决0-1背包问题.doc
动态规划解决0-1背包问题 - 《算法分析设计》 实验报告 2015-2016 年第 2 学期 实验班级: 学生姓名: 学号: 指导老师: 信息工程学院 实验项目名称:动态规划....
基于动态规划法求解动态0-1背包问题.pdf
基于动态规划法求解动态0-1背包问题 - 随机时变背包问题(RTVKP)是一种动态组合优化问题,也是一种典型的NP-hard问题.由于RTVKP问题中物品的价值、重量背包载重...
0-1背包问题之动态规划法_-_图文.ppt
0-1背包问题动态规划法_-_计算机软件及应用_IT/计算机_专业资料。0-1背包问题动态规划法_- 动态规划 1. 概述 2. 组合问题中的动态规划法 3. 图问题中...
0_1背包问题的多种解法.doc
回溯法求解 0-1 背包问题的过程 递归法:在利用递归法解决 0-1 背包问题时...由此导出了许多相互重叠的子问题,所以,0-1 背包问题可以用动态规划法得到最优...
更多相关标签: