当前位置:首页 >> 学科竞赛 >> 资源背包动态规划

资源背包动态规划


背包类动态规划问题

经典的背包问题(01背包)
? ? ? ? 有N件物品; 第i件物品Wi公斤; 第i件物品价值Ci元; 现有一辆载重M公斤的卡车;

? 问选取装载哪些物品,使得卡车运送的 总价值最大?

搜索法
? 对于每种物品,要么装上卡车,要么不装,因此,N种 物品的装箱方案共有2N种

。 ? 按每种物品进行搜索,方法如下: – 对第i种物品进行搜索 – 如果所有的物品都搜索完,则更新最优解 – 如果当前的估计达不到最优解,则回溯 – 如果第i种物品能放,则放,并标记,否则选下一个 物品 – 清除标记 – 回溯

动态规划
? 可以按每个物品进行规划,同样每种物品有选和 不选两种选择 ? 设F(i,j)表示前i件物品载重为j的最大效益,则有
? F (i ? 1, j ? w[i ]) ? C[i ], 第i种物品装载 F (i, j ) ? Max? ? F (i ? 1, j ), 第i种物品不装载

? ? ? ?

1<=i<=N, 0<=j<=N 初值:F(0,j)=0 F(N,M)即答案 显然时间复杂度为O(NM)

主程序如下
for i:=1 to m do f[0,i]:=0; //初始化 for i:=1 to n do f[i,0]:=0; for i:=1 to n do // 动态规划,递推求f for j:=1 to m do begin if j>=w[i] then //背包容量够大 f[i,j]:=max(f[i-1,j-w[i]]+c[i],f[i-1,j]) else //背包容量不足 f[i,j]:=f[i-1,j]; end;

满背包问题(01背包)
? ? ? ? 有N件物品; 第i件物品Wi公斤; 第i件物品价值Ci元; 现有一辆载重M公斤的卡车;

? 问选取装载哪些物品,使得卡车开车正 好装满时,运送的总价值最大? 若无法装满卡车,则输出无解。

动态规划
? 设F(i,j)表示前i件物品背包为j的最大效益, 则有
? F (i ? 1, j ? w[i ]) ? C[i ], 第i种物品装载 F (i, j ) ? Max? ? F (i ? 1, j ), 第i种物品不装载

? ? ? ?

1<=i<=N, 0<=j<=N 初值:F(0,j)=0, F(1,j)= -∞ F(N,M)即答案 显然时间复杂度为O(NM)

带条件的背包问题(1)
? ? ? ? ? ? 有N件物品; 第i件物品Wi公斤; 第i件物品价值Ci元; 第i件物品可能带0~2个附件; 若装载附件,必须装载主件,反之没有约束; 现有一辆载重M公斤的卡车;

? 问选取装载哪些物品,使得卡车运送的总价值最 大?

分析
? 假设只有主件的情况 ,显然与经典背包问题完 全相同! ? 现在每个物品有附件,我们可以分成4种方案 – 仅装载主件 – 装载主件+第1个附件 – 装载主件+第2个附件 – 装载主件+2个附件 ? 由于上述4种并列,这是几种不同的决策同时规 划即可

动态规划
? 设F(i,j)表示前i件物品背包为j的最优解,则有,
? F (i ? 1, j ), 不选第i件物品 ? ? F (i ? 1, j ? w[i ]) ? c[i ],只选主件 ? F (i ? 1, j ? w[i ] - w[i1]) ? c[i ] ? c[i1], ? 1 ? // 选主件和第 件附件 F (i, j ) ? Max? ? F (i ? 1, j ? w[i ] - w[i 2]) ? c[i ] ? c[i 2], ? // 选主件和第2件附件 ? ? F (i ? 1, j ? w[i ] - w[i1] - w[i 2]) ? c[i ] ? c[i1] ? c[i 2], ? // 选主件和2件附件 ?

? 1<=i<=N, 0<=j<=M ? 时间复杂度O(NM)

多层背包问题
? ? ? ? ? 有N件物品; 第i件物品Wi公斤; 第i件物品价值Ci元; 现有一辆载重M公斤的卡车; 第i件物品限制最多只能取Xi个;

? 问选取装载哪些物品,使得卡车运送的总 价值最大?

分析
? 我们可以类似01背包问题,将第i种物品拆分成 x[i]个,这样每个物品只有1件了,如下图:

? 然后对所有的物品采用动态规划即可。 ? F(i,j)=max{ f(i-1,j-k*w[i]) + k*c[i] } ? 0<=k*w[i]<=j

完全背包问题
? ? ? ? ? 有N件物品; 第i件物品Wi公斤; 第i件物品价值Ci元; 现有一辆载重M公斤的卡车; 每次可以选取某种物品的任意多件装载;

? 问选取装载哪些物品,使得卡车运送的总 价值最大?

分析
? 类似多层背包问题将每个物品展开成X[i ]=m/w[i]个,然 后对所有的物品采用动态规划即可。 ? 若两件物品i、j满足c[i]<=c[j]且w[i]>=w[j],则将物品i去掉, 不用考虑。这个优化的正确性显然:任何情况下都可将 价值小费用高的j换成物美价廉的i,得到至少不会更差的 方案。 ? 由于每种物品有选和不选两种情况,可以将每种物品的 2k个当成一个整体考虑。这样对于某种物品要选取多个 ,都可以由若干个2k个物品进行组合 (即2进制数)。例如 第i种物品要选10个,则10=23+21 。 ? 这样第i种物品的个数为k=㏒2 (m/wi)物品,是一个很大 的改进。 ? 进一步, 在计算k时, K =㏒2 (j/wi), j为当前背包剩余空间。

进一步
for i:=1 to n do // 动态规划,递推求f for j:=m downto 1 do begin if j>=w[i] then //背包容量够大 f[i,j]:=max(f[i-1,j-w[i]]+c[i],f[i-1,j]) else //背包容量不足 f[i,j]:=f[i-1,j]; end; 在这里为了使得每个物品只取1个或不取,采用了每次取j都 是与i-1进行比较,实际上保存了每1步取不同j的值

改进程序
? 事实上,我们只关心剩余背包的最大值,也就是 仅仅关心f(j),因此,在对f(j)更新时,只要背包容 量可以,那么可以反复更新。程序如下: for i:=1 to n do // 动态规划,递推求f for j:=0 to m do begin if j>=w[i] then //背包容量够大 f[j]:=max(f[j-w[i]]+c[i],f[j]) end;

思考题1:机器分配
? ? ? ? M台设备,分给N个公司。 若公司i获得j台设备,则能产生Aij效益 问如何分配设备使得总效益最大? M<=15,N<=10。

分析
? 用机器数来做状态,数组f(i,j)表示前i个公 司分配j台机器的最大盈利。则状态转移方 程为: ? f(i,j) =Max{f[i-1,k] + a[i,j-k]} (1<=i<=N,1<=j<=M,0<=k<=j ) ? 初始值: f(0,0)=0 ? 时间复杂度O(N*M2)

思考题2:硬币找零
?给定N枚硬币 ?给定T元钱 ?用这N枚硬币找这T元钱,使得剩下的钱最 少。
?剩下钱数最少的找零方案中的所需的最少 硬币数。 ?N<=500,T<=10000.

分析
?设F[i]表示需要找的钱数为i时所需要的最少 钱币数。显然有: ?F[i]=Min{F[ i - A[j] ] + 1} { i≤ T,1≤j≤N} ?初始值:F[0]=0。 ?A[j]表示其中 第j种钱币的面值。 ?时间复杂度为O(N*T)。

思考题3:系统可靠性
? 一个系统由若干部件串联而成,只要有一个部件 故障,系统就不能正常运行,为提高系统的可靠 性,每一部件都装有备用件,一旦原部件故障, 备用件就自动进入系统。显然备用件越多,系统 可靠性越高,但费用也越大,那么在一定总费用 限制下,系统的最高可靠性等于多少? ? 给定一些系统备用件的单价Ck,以及当用Mk个此 备用件时部件的正常工作概率Pk(Mk),总费用 上限C。求系统可能的最高可靠性。

样例
输入文件格式:
第一行:n C 第二行:C1 P1(0) ) … 第n 行:Cn Pn(0) )

P1(1) … P1(X1) (0<=X1<=[C/Ck] Pn(1) … Pn(Xn) (0<=Xn<=[C/Cn]

输入:2 20 3 0.6 0.65 0.7 0.75 0.8 5 0.7 0.75 0.8 0.9 0.95 输出:0.6375=0.75*0.85

0.85

0.9

分析
? 设f(i,j)表示将j的资金用到前i项备用件 中去的最大可靠性,则有 F(i,j)= max{F(i-1,j–k*Cost[i])*P[i,k]} ? 0<=i<=n, 0<=j<=C,0<=k<j div Cost(i) ? 初始: F(0,0)=1 ? 目标: F(n,C) ? 时间复杂度:O(k*n*C),这里k是常数因子 ,与数据相关

总结
? 对于资源类动态规划问题,我们可以看出,问题描述必须 有一个基本要素:资源,有时这种资源可能是金钱、空间 或者时间,问题就是要对这些资源如何分配,一种基本的 想法是将资源应用于前i个阶段,然后考虑第i个阶段和前i1个阶段之间的关系。 ? 设前i个点的消耗j的资源得到的最优值,研究前i-1个点消 耗的资源的最优值,利用第i个点决策转移,如下图。

? 状态转移方程一般可写成: fi(j) = min{ fi-1 ( k) + ui (j,k)}


更多相关文档:

资源背包类型动态规划

资源背包类型动态规划_IT认证_资格考试/认证_教育专区。动态规划入门资源背包类型动态规划 资源背包类型动态规划动态规划中的经典问题,在近几年联赛中经常出现,甚至...

动态规划经典案例详解(背包问题)

动态规划经典案例详解(背包问题)_生产/经营管理_经管营销_专业资料。信息学奥林...资源背包动态规划 32页 免费 第三章动态规划 背包问题... 13页 免费喜欢...

背包问题动态规划

背包问题动态规划_数学_自然科学_专业资料。动态规划 动态规划的逆向思维法 动态...资源背包动态规划 32页 免费 第三章动态规划 背包问题... 13页 免费 0-1....

动态规划解0-1背包问题

0209404 班 020940410 杨洲 2011-11-7 上机时间: 一、实验目的与要求: 1、掌握动态规划算法求解问题的一般特征和步骤; 2、使用动态规划法编程,求解 0/1 背包...

0-1背包问题动态规划详解及代码

0-1背包问题动态规划详解及代码_计算机软件及应用_IT/计算机_专业资料。0/1 背包问题动态规划详解及 C 代码动态规划是用空间换时间的一种方法的抽象。 其关键是...

动态规划之01背包问题(最易理解的讲解)

01 背包问题,是用来介绍动态规划算法最经典的例子,网上关于 01 背包问题的 讲解也很多,我写这篇文章力争做到用最简单的方式,最少的公式把 01 背包问 题讲解透彻...

利用动态规划解决01背包问题

利用动态规划解决01背包问题_专业资料。龙源期刊网 http://www.qikan.com.cn ...越来越高,因此算法也越来越受人重视,好的算法可以加快计算速度和减少系统资源。...

动态规划法解决01背包

动态规划法解决01背包_法律资料_人文社科_专业资料。算法设计与分析--01 背包问题问题描述: 给定 N 中物品和一个背包。物品 i 的重量是 Wi,其价值位 Vi ,背包...

0-1背包问题动态规划详解及代码

0-1背包问题动态规划详解及代码_计算机软件及应用_IT/计算机_专业资料。0/1 背包问题动态规划详解及 C 代码动态规划是用空间换时间的一种方法的抽象。 其关键是...

动态规划之01背包和完全背包

动态规划之01背包和完全背包_IT/计算机_专业资料。分享 0-1 背包 状态转移方程: f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]} “将前 i ...
更多相关标签:
背包问题 动态规划 | 01背包问题动态规划 | 01背包动态规划算法 | 动态规划 背包 | 01背包动态规划 | 动态规划求解背包问题 | 01背包问题动态规划 c | 完全背包问题动态规划 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com