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

动态规划和回溯法解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背包问题实验报告(含源代码).doc
动态规划解决算法0-1背包问题实验报告(含源代码)_计算机软件及应用_IT/计算机_...动态规划和回溯法解0-1背... 10页 1下载券 动态规划法解0-1背包问题....
动态规划求解0-1背包问题.doc
动态规划求解0-1背包问题_计算机软件及应用_IT/计算机_专业资料。基于MATLAB的0...有多种方法可以处理 它,比如分支限界法、回溯法、贪心算法等等都可以对其进行...
算法分析与程序设计动态规划及回溯法解01背包问题.doc
算法分析与程序设计动态规划及回溯法解01背包问题 - 动态规划法、回溯法解 0-1 背包问题 2012 级 计科 庞佳奇 一、 1. 问题描述与分析 动态规划算法通常用于...
0-1背包问题的解决(回溯法).doc
回溯法| 背包| 0-1背包问题的解决(回溯法)_解决方案_计划/解决方案_实用文档。算法设计分析,通过回溯法动态规划的方法解决0-1背包问题。 前面...
0_1背包问题的多种解法.doc
回溯法求解 0-1 背包问题的过程 递归法:在利用递归法解决 0-1 背包问题时...由此导出了许多相互重叠的子问题,所以,0-1 背包问题可以用动态规划法得到最优...
0-1背包问题动态规划详解及代码.pdf
0-1背包问题动态规划详解及代码 - 0/1 背包问题动态规划详解及 C 代码 动态规划是用空间换时间的一种方法的抽象。 其关键是发现子问题和记录其结果。 然后 ...
用动态规划法与回溯法实现0-1背包问题的比较_论文.pdf
动态规划与回溯法实现0-1背包问题的比较 - 0-1背包问题是运筹学中的著名问题。也是计算机算法中的一个经典问题。本文采用动态规划和回溯法对该问题进行求解...
动态规划解决0-1背包问题.doc
动态规划解决0-1背包问题 - 《算法分析设计》 实验报告 2015-2016 年第 2 学期 实验班级: 学生姓名: 学号: 指导老师: 信息工程学院 实验项目名称:动态规划....
最新动态规划解决算法0-1背包问题实验报告(含源代码).doc
最新动态规划解决算法0-1背包问题实验报告(含源代码)_计算机软件及应用_IT...2014 年 5 月 9 日 一.实验目的及实验环境 1.使用动态规划和回溯法生成两...
0-1背包问题动态规划详解及代码.doc
0-1背包问题动态规划详解及代码 - 0/1 背包问题动态规划详解及 C 代码 动态规划是用空间换时间的一种方法的抽象。 其关键是发现子问题和记录其结果。 然后 ...
0-1背包问题-贪心法和动态规划法求解.doc
0-1背包问题-贪心法和动态规划法求解_工学_高等教育_教育专区。此文档主要描写了贪心法解决00\1背包问题,附带有动态规划法的解决办法! ...
用蛮力法、动态规划法和贪心法求解0 1背包问题.doc
实验项目三 用蛮力法、 动态规划法和贪心法求解 0/1 背包问题 实验目的 1、
0-1背包问题动态规划详解及代码.doc
0-1背包问题动态规划详解及代码_计算机软件及应用_IT/计算机_专业资料。0/1 背包问题动态规划详解及 C 代码动态规划是用空间换时间的一种方法的抽象。 其关键是...
蛮力法、动态规划法、回溯法和分支限界法求解01背包问题.doc
蛮力法、动态规划法、回溯法和分支限界法求解01背包问题 - 一、实验内容: 分别用蛮力法、动态规划法、回溯法和分支限界法求解 0/1 背包问题。 注:0/1 背包...
0-1背包问题-贪心法和动态规划法求解1.doc
0-1背包问题-贪心法和动态规划法求解1_经管营销_专业资料。实验四 “0-1”
解01背包问题的动态规划算法.doc
解01背包问题的动态规划算法 - 解 0/1 背包问题动态规划算法 摘要: 摘要:本文通过研究动态规划原理,提出了根据该原理解决0/1背包问题的方法算法实现, 并对...
0-1背包问题四种不同算法的实现要点.doc
01 背包问题:给定 n 种物品一个背包,背包最...性质是该 问题可用动态规划算法或贪心算法求解的关键...[i]; 方案三:回溯法 1、回溯法的基本原理与分析...
0_1背包问题的多种解法.doc
回溯法求解 0-1 背包问题的过程 递归法:在利用递归法解决 0-1 背包问题时...由此导出了许多相互重叠的子问题,所以,0-1 背包问题可以用动态规划法得到最优...
基于Matlab的0_1背包问题的动态规划方法求解_王乐.pdf
基于Matlab的0_1背包问题动态规划方法求解_王乐 - 第 16 卷第 4 期 2006 年 4 月 计算机技术发展 CO M PU T ER TECHN OLO GY AN D D...
更多相关标签: