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

算法分析与程序设计动态规划及回溯法解01背包问题


动态规划法、回溯法解 0-1 背包问题
2012 级 计科 庞佳奇

一、
1.

问题描述与分析

动态规划算法通常用于求解具有某种最优性质的问题。 在这类问题中, 可能会 有许多可行解。每一个解都对应于一个值,我们希望找到具有最优值的解。动态规 划算法与分治法类似, 其基本思想也是将待求解问题分解成若干个子问题, 先求解 子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,适合于用动 态规划求解的问题, 经分解得到子问题往往不是互相独立的。 若用分治法来解这类 问题,则分解得到的子问题数目太多,有些子问题被重复计算了很多次。如果我们 能够保存已解决的子问题的答案, 而在需要时再找出已求得的答案, 这样就可以避 免大量的重复计算, 节省时间。 我们可以用一个表来记录所有已解的子问题的答案。 不管该子问题以后是否被用到,只要它被计算过,就将其结果填入表中。这就是动 态规划法的基本思路。 具体的动态规划算法多种多样, 但它们具有相同的填表格式。 多阶段决策问题中,各个阶段采取的决策,一般来说是与时间有关的,决策 依赖于当前状态,又随即引起状态的转移,一个决策序列就是在变化的状态中产 生出来的,故有“动态”的含义,称这种解决多阶段决策最优化问题的方法为动 态规划方法。任何思想方法都有一定的局限性,超出了特定条件,它就失去了作 用。同样,动态规划也并不是万能的。适用动态规划的问题必须满足最优化原理 和无后效性。1.最优化原理(最优子结构性质) 最优化原理可这样阐述:一个最 优化策略具有这样的性质,不论过去状态和决策如何,对前面的决策所形成的状 态而言,余下的诸决策必须构成最优策略。简而言之,一个最优化策略的子策略 总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。2.无后效性 将各阶段按照一定的次序排列好之后,对于某个给定的阶段状态,它以前各阶段 的状态无法直接影响它未来的决策,而只能通过当前的这个状态。换句话说,每 个状态都是过去历史的一个完整总结。这就是无后向性,又称为无后效性。3.子 问题的重叠性 动态规划将原来具有指数级时间复杂度的搜索算法改进成了具有 多项式时间复杂度的算法。其中的关键在于解决冗余,这是动态规划算法的根本 目的。动态规划实质上是一种以空间换时间的技术,它在实现的过程中,不得不 存储产生过程中的各种状态,所以它的空间复杂度要大于其它的算法。 01 背包是在 M 件物品取出若干件放在空间为 W 的背包里,每件物品的体积为 W1,W2??Wn,与之相对应的价值为 P1,P2??Pn。求出获得最大价值的方案。 2. 回溯法(探索与回溯法)是一种选优搜索法,按选优条件向前搜索,以达到目 标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选 择, 这种走不通就退回再走的技术为回溯法, 而满足回溯条件的某个状态的点称为 “回溯点”。 在包含问题的所有解的解空间树中, 按照深度优先搜索的策略, 从根结点出发深度 探索解空间树。当探索到某一结点时,要先判断该结点是否包含问题的解,如果包 含,就从该结点出发继续探索下去,如果该结点不包含问题的解,则逐层向其祖先 结点回溯。(其实回溯法就是对隐式图的深度优先搜索算法)。 若用回溯法求问 题的所有解时,要回溯到根,且根结点的所有可行的子树都要已被搜索遍才结束。

而若使用回溯法求任一个解时,只要搜索到问题的一个解就可以结束 可用回溯法求解的问题 P,通常要能表达为:对于已知的由 n 元组(x1,x2,?, xn)组成的一个状态空间 E={(x1,x2,?,xn)∣xi∈Si ,i=1,2,?,n},给定 关于 n 元组中的一个分量的一个约束集 D, 要求 E 中满足 D 的全部约束条件的所有 n 元 组。其中 Si 是分量 xi 的定义域,且 |Si| 有限,i=1,2,?,n。我们称 E 中满足 D 的全部约束条件的任一 n 元组为问题 P 的一个解。 解问题 P 的最朴素的方法就是枚举法, 即对 E 中的所有 n 元组逐一地检测其是否满足 D 的全部约束,若满足,则为问题 P 的一个解。但显然,其计算量是相当大的。 我们发现,对于许多问题,所给定的约束集 D 具有完备性,即 i 元组(x1,x2,?,xi) 满足 D 中仅涉及到 x1,x2,?,xi 的所有约束意味着 j(j<=i)元组(x1,x2,?, xj)一定也满足 D 中仅涉及到 x1,x2,?,xj 的所有约束,i=1,2,?,n。换句话说, 只要存在 0≤j≤n-1,使得(x1,x2,?,xj)违反 D 中仅涉及到 x1,x2,?,xj 的 约束之一,则以(x1,x2,?,xj)为前缀的任何 n 元组(x1,x2,?,xj,xj+1,?, xn)一定也违反 D 中仅涉及到 x1,x2,?,xi 的一个约束,n≥i≥j。因此,对于约束 集 D 具有完备性的问题 P,一旦检测断定某个 j 元组(x1,x2,?,xj)违反 D 中仅涉 及 x1,x2,?,xj 的一个约束,就可以肯定,以(x1,x2,?,xj)为前缀的任何 n 元组(x1,x2,?,xj,xj+1,?,xn)都不会是问题 P 的解,因而就不必去搜索它们、 检测它们。 回溯法正是针对这类问题, 利用这类问题的上述性质而提出来的比枚举法效 率更高的算法。 二、

算法设计(或算法步骤)

1. 这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放。用 子问题定义状态:即 f[i][v]表示前 i 件物品恰放入一个容量为 v 的背包可以获得的最 大价值。则其状态转移方程便是: f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]} 这个方程非常重要,基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有 必要将它详细解释一下:“将前 i 件物品放入容量为 v 的背包中”这个子问题,若只考 虑第 i 件物品的策略(放或不放),那么就可以转化为一个只牵扯前 i-1 件物品的问题。 如果不放第 i 件物品,那么问题就转化为“前 i-1 件物品放入容量为 v 的背包中”,价 值为 f[i-1][v];如果放第 i 件物品,那么问题就转化为“前 i-1 件物品放入剩下的容 量为 v-c[i]的背包中”,此时能获得的最大价值就是 f[i-1][v-c[i]]再加上通过放入第 i 件物品获得的价值 w[i]。 2. (1) 分析要解决的问题,给出你的思路,可以借助图表等辅助表达。 01 背包问题用回溯法实现就是要枚举其所有的解空间, 时间复杂度为(2)nO 左右。搜 索的具体方法如下: 对于每一个物品 i,对于该物品只有选与不选 2 个决策,总共有 n 个物品,可以顺 序依次考虑每个物品,这样就形成了一棵解空间树: 基本思想就是遍历这棵树,以枚举所有情况,最后进行判断,如果重量不超过背包 容量,且价值最大的话,该方案就是最后的答案。 利用回溯算法写还可以加入一些优化,进行剪枝,因为很多情况是没有意义的,例如当 重量大于背包容量的时候,没有必要对剩下的物品再来决策了。或者将剩下的所有物品 都选取其总价值也没有目前已经求得的方案的价值还大的话,也是可以剪枝的。 (2)分析利用你的想法解决该问题可能会有怎样的时空复杂度。 时间复杂度估计:

(2)nO 因为物品只有选与不选 2 个决策, 而总共有 n 个物品, 所以时间复杂度为(2)nO。空 间复杂度估计:()On 因为递归栈最多达到 n 层,而且存储所有物品的信息也只需要常数 个一维数组,所以最终的空间复杂度为()On。

三、

算法实现 1. 动态规划 #include<stdio.h> #include<stdlib.h> int c[50][50]; int w[10],v[10]; int x[10]; int n; void KNAPSACK_DP(int n,int W); void OUTPUT_SACK(int c[50][50],int k) ; void KNAPSACK_DP(int n,int W) { int i,k; for(k=0;k<=W;k++) c[0][k]=0; for(i=1;i<=n;i++) { c[i][0]=0; for(k=1;k<=W;k++) { if(w[i]<=k) { if(v[i]+c[i-1][k-w[i]]>c[i-1][k]) c[i][k]=v[i]+c[i-1][k-w[i]]; else c[i][k]=c[i-1][k]; } else c[i][k]=c[i-1][k]; } } } void OUTPUT_SACK(int c[50][50],int k) { int i; for(i=n;i>=2;i--) { if(c[i][k]==c[i-1][k]) x[i]=0;

else { x[i]=1; k=k-w[i]; } } x[1]=(c[1][k]?1:0); for(i=1;i<=n;i++) printf("%4d",x[i]); } void main() { int m; int i,j,k; printf("输入物品个数:"); scanf("%d",&n); printf("依次输入物品的重量:\n"); for(i=1;i<=n;i++) scanf("%d",&w[i]); printf("依次输入物品的价值:\n"); for(i=1;i<=n;i++) scanf("%d",&v[i]); printf("输入背包最大容量:\n"); scanf("%d",&m); for(i=1;i<=m;i++) printf("%4d",i); printf("\n"); KNAPSACK_DP(n,m); printf("构造最优解过程如下:\n"); for(j=1;j<=5;j++) { for(k=1;k<=m;k++) printf("%4d",c[j][k]); printf("\n"); } printf("最优解为:\n"); OUTPUT_SACK(c,m); system("pause"); }

2. 回溯法 #include <stdio.h> #include <malloc.h> #include <windows.h> typedef struct goods { double *value; //价值 double *weight; //重量 char *select; //是否选中到方案 int num;//物品数量 double limitw; //限制重量 }GOODS; double maxvalue,totalvalue; char *select1; void backpack(GOODS *g, int i, double tw, double tv) { int k; if (tw + g->weight[i] <= g->limitw) { select1[i] = 1; if (i < g->num - 1) backpack(g, i + 1, tw + g->weight[i], tv); else { for (k = 0; k < g->num; ++k)

g->select[k] = select1[k]; maxvalue = tv; } } select1[i] = 0; if (tv - g->value[i] > maxvalue) { if (i < g->num - 1) backpack(g, i + 1, tw, tv - g->value[i]); else { for (k = 0; k < g->num; ++k) g->select[k] = select1[k]; maxvalue = tv - g->value[i]; } } } int main() { double sumweight; GOODS g; int i; printf("背包最大重量:"); scanf("%lf",&g.limitw); printf("可选物品数量:"); scanf("%d",&g.num); if(!(g.value = (double *)malloc(sizeof(double)*g.num))) { printf("内存分配失败\n"); exit(0); } if(!(g.weight = (double *)malloc(sizeof(double)*g.num))) { printf("内存分配失败\n"); exit(0); } if(!(g.select = (char *)malloc(sizeof(char)*g.num))) { printf("内存分配失败\n"); exit(0); } if(!(select1 = (char *)malloc(sizeof(char)*g.num))) { printf("内存分配失败\n");

exit(0); } totalvalue=0; for (i = 0; i < g.num; i++) { printf("输入第%d 号物品的重量和价值:",i + 1); scanf("%lf%lf",&g.weight[i],&g.value[i]); totalvalue+=g.value[i]; } printf("\n 背包最大能装的重量为:%.2f\n\n",g.limitw); for (i = 0; i < g.num; i++) printf("第%d 号物品重:%.2f,价值:%.2f\n", i + 1, g.weight[i], g.value[i]); for (i = 0; i < g.num; i++) select1[i]=0; maxvalue=0; backpack(&g,0,0.0,totalvalue); sumweight=0; printf("\n 可将以下物品装入背包,使背包装的物品价值最大:\n"); for (i = 0; i < g.num; ++i) if (g.select[i]) { printf("第%d 号物品,重量:%.2f,价值:%.2f\n", i + 1, g.weight[i], g.value[i]); sumweight+=g.weight[i]; } printf("\n 总重量为: %.2f,总价值为:%.2f\n", sumweight, maxvalue ); return 0; }

四、算法分析(与改进)
(1) 算法实现的复杂度在问题规模很大时可以接受吗? 答:不可以接受。因为该算法是指数级别的时间复杂度为(*2)nOn,当 n 较大时,也能 在一定时间内无法得出结果。空间复杂度为()On,还可以接受。 但是综合上面分析,时间复杂度成为极大地瓶颈。所以规模很大时不可以接受。

(2)所选用的数据结构合适吗? 答:合适,只用到一维数组。使用的数据结构简单,易理解。能够对数组中的每个 元素随机访问。 (3) 该算法都存在哪几类可能出现的情况,你的测试完全覆盖了你所想到的这些

情况吗,测试结果如何? 答:测试全面。 输入规模为 0 时,程序自动结束。 输入总重量小于背包容量时,结果为所有物品的价值总和。 输入的总重量大于背包容 量时,结果为能装入所有方案中最大的值。 (4) 叙述通过实验你对回溯法方法的理解及其优缺点 优点: 回溯法在普通的深度优先搜索的基础上增加了限界函数, 对不必要的解空间树

进行剪枝,使得可行解的数量大大减少,增加了搜索速度。 回溯法的设计也非常简单,即 简单的枚举搜索策略,只需要分析细节过程就能增加剪枝的操作。 另外,空间复杂度通常 非常小, 只有搜索深度左右的空间。 缺点: 回溯法虽然设计简单, 但是时间复杂度非常高, 通常是指数级别的。而且回溯法的难点在于限界函数的设计。 而且回溯法通常需要遍历完 所有的解空间才能得出最优值,而不是像宽度优先搜索一样第一次求出的值便是最优值。

报 告 成 绩 单

评 语

成绩


相关文章:
算法分析与程序设计动态规划及回溯法解01背包问题.doc
算法分析与程序设计动态规划及回溯法解01背包问题 - 动态规划法、回溯法解 0-
动态规划与回溯法解决0-1背包问题.doc
动态规划与回溯法解决0-1背包问题 - 0-1 背包动态规划解决问题 一、问题描述: 有 n 个物品,它们有各自的重量价值,现有给定容量的背包,如何让背包里装入的...
算法设计与分析--01背包问题(动态规划法解决)_图文.pdf
算法设计与分析--01背包问题(动态规划法解决)_电子/电路_工程科技_专业资料。 您的评论 发布评论 用户评价 好,作者还有其他关于动态规划法的文档吗? 2018-06-...
蛮力法、动态规划法、回溯法和分支限界法求解01背包问题.doc
蛮力法、动态规划法、回溯法和分支限界法求解01背包问题_天文/地理_自然科学_...二、所用算法的基本思想及复杂度分析: 1.蛮力法求解 0/1 背包问题: 1)基本...
01背包问题不同算法设计、分析与对比.doc
01背包问题不同算法设计分析与对比 - 实践动态规划、贪心、回溯以及分支限界算法程序设计
动态规划算法-01背包问题.doc
动态规划算法-01背包问题 - 动态规划法求解 0-1 背包问题 一、动态规划法的设计思想 动态规划法是数学-“运筹学” 中一个决策分析的实现, 广泛运用在计算机算法...
01背包问题(动态规划法).doc
01背包问题(动态规划法) - 算法设计分析,通过回溯法和动态规划的方法解决0-1背包问题
动态规划解决算法0-1背包问题实验报告(含源代码).doc
实验内容 1.设计一个 O(n^2)时间的算法,找出由 n 个数组成的序列的最长...0_1背包问题动态规划算法... 2页 免费 动态规划和回溯法解0-1背... ...
动态规划法解决01背包.doc
动态规划法解决01背包 - 算法设计与分析--01 背包问题 问题描述: 给定 N 中物品一个背包。物品 i 的重量是 Wi,其价值位 Vi ,背包的容量为 C。问应该...
用动态规划法与回溯法实现0-1背包问题的比较_论文.pdf
动态规划法与回溯法实现0-1背包问题的比较 - 0-1背包问题是运筹学中的著名问题。也是计算机算法中的一个经典问题。本文采用动态规划和回溯法对该问题进行求解...
蛮力法、动态规划法、回溯法和分支限界法求解01背包问题.doc
蛮力法、动态规划法、回溯法和分支限界法求解01背包问题_电脑基础知识_IT/计算机...二、所用算法的基本思想及复杂度分析: 1.蛮力法求解 0/1 背包问题: 1)基本...
01背包问题不同算法设计、分析与对比报告.doc
实验三 01 背包问题不同算法设计分析与对比一.问题描述给定 n 种物品和一...动态规划、贪心、回溯和分支限界算法。 2.分别给出不同算法求解该问题的思想与...
算法实验报告01背包问题.doc
动态规划、贪心算法、回溯法三种方法的实现。仅供参考,有能力还是鼓励自己做 河北工业大学计算机科学与软件学院 算法分析与设计实验 报告实验:0/1 背包问题 姓名: ...
解01背包问题的动态规划算法.doc
解01背包问题动态规划算法_IT/计算机_专业资料。...否则转(6);(6)用回溯法确定决策序列;终止程序。 ...算法分析与程序设计动态... 暂无评价 10页 1下载...
蛮力动规贪心回溯法的01背包和TSP问题.doc
蛮力动规贪心回溯法01背包和TSP问题_计算机软件应用_IT/计算机_专业资料。主要介绍的是回溯的核心算法,同时有蛮力,动态规划,贪心,回溯的时间复杂度的比较。...
回溯法解决01背包问题.doc
它在包含问题的所有解的解空间树中按照 深度优先的...01背包回溯法 2页 免费 蛮力法、动态规划法、回...算法设计与分析实验报告... 6页 5下载券 分别用...
01背包问题动态规划详解.doc
01背包问题动态规划详解_计算机软件应用_IT/计算机...事实上,使用一维数组解 01 背包程序在后面会被...它包含了背包问题中设计状态、方程的最基 本思想,...
01背包问题动态规划详解及C++代码.doc
01背包问题动态规划详解C++代码_计算机软件应用_IT/计算机_专业资料。0/1 背包问题动态规划详解 C++代码 1. 问题描述 给定一个载重量为 C 的背包? n 个...
算法分析与设计实验报告之01背包问题.doc
算法分析与设计实验报告之01背包问题_工学_高等教育...5 4.动态规划法分析:......回溯法分析: 回用回溯法解 0_1 背包问题时,会用到状态空间树。在搜索状态...
用蛮力法、动态规划法和贪心法求解01背包问题.doc
c++语言描述的蛮力法,动态规划法,贪心法解决01背包问题,内附源代码,调试结果以及分析测试 算法设计与分析 项目名称:用蛮力法、动态规 划法和贪心法求解 0/1 ...
更多相关标签: