我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:大丰收高手论坛 > 动态规划 >

动态规划经典模型-背包模型

归档日期:06-10       文本归类:动态规划      文章编辑:爱尚语录

  有N种物品(每种物品1件)和一个容量为V的背包。放入第 i 种物品耗费的空间是Ci,得到的价值是Wi。求解将哪些物品装入背包可使价值总和最大。

  f[i][v]表示前i种物品恰好放入一个容量为v的背包可以获得的最大价值。

  决策为第i个物品在前i-1个物品放置完毕后,是选择放还是不放,状态转移方程为:

  时间复杂度O(VN),空间复杂度O(VN) (空间复杂度可利用滚动数组进行优化达到O(V),下文会介绍滚动数组优化)。

  有N种物品(每种物品无限件)和一个容量为V的背包。放入第 i 种物品耗费的空间是Ci,得到

  f[i][v]表示前i种物品恰好放入一个容量为v的背包可以获得的最大价值。

  时间复杂度O( VNsum{V/Ci} ),空间复杂度在用滚动数组优化后可以达到

  有N种物品(每种物品Mi件)和一个容量为V的背包。放入第i种物品耗费的空间是Ci,得到

  f[i][v]表示前i种物品恰好放入一个容量为v的背包可以获得的最大价值。

  有 n 件物品x1, x2, …, xn , 每件物品有一个价值和一个重量,分别记为:

  其中所有的 wi 均为整数。 现有一个背包,其最大载重量为m,要求从这n件物品中任取若干件(这些物品每样只有一件,要么被装入要么被留下)。问背包中装入哪些物品可使得所装物品的价值和最大? (我们只需要求出最大价值,不需要求出具体拿的是哪些物品)

  如果想用贪心,先求出平均价值,然后从高到低的方法来取,如果有一个背包的容量为10,共有3个物品,体积分别是3、3、5,价值分别是6、6、9,那么你的方法取到的是前两个物品,总价值是12,但明显最大值是后两个物品组成的15。因此贪心的方法不能得到正确结果。

  (1)放入:问题转换为在背包载重为m-wi的情况下,在其它n-1件物品中挑选,求得价值和最大。等把这个子问题求出后,再加上vi的价值就是整个问题的最优解了。

  (2)没放入:那么就当xi 根本不存在,直接解物品数量为n-1,背包载重为m的子问题。子问题的最优解就是问题的最优解。

  定义函数f(i,j)为在1~i 件物品中选若干件装入限重为 j 的背包中的最大价值和, 那么根据上面关于第 i 件物品是否装入了背包的情况分析,我们得出关系式:

  当然,第i件物品要装入是有条件限制的:第i 件物品重量小于等于背包限重,即 w[i] = j

  求得装入或者不装入第 i 件物品的限重为J的背包的最大价值,只需要比较这两种情况下谁的价值更大,更大者为当前问题的最优解。

  按问题规模从小到大地求解问题,把每阶段求得的问题的最优解保存在表格(数组)中,以便在下一阶段求解更大的问题时,可以直接查表引用子问题的最优解。 (类似于递推)

  将n件物品放入背包,故可以把阶段划分为n个。把在前I件物品中选取物品放入背包作为第I个阶段。

  而这m个问题的求解基础是第I-1个阶段的m个子问题。这些子问题的最优解已经先于此时求得,保存在f[I-1,1], f[I-1,2], …, f[I-1,m]中,现在只需要直接引用它们的值就可以了。这就是动态规划自底向上的体现。

  只有两个,在前I件物品中,限重为J的条件下,装入第I件物品还是不装入第I件物品。比较这两种情况的价值和,谁大谁就是最优解。

  北京:省选班:1月18日-2月2日,普及组、提高组基础班、提高组精英班2月6日~2月13日;

  来自清华北大在读金牌及一线名师,且专属于清北学堂教研团队,规模20多人,多次参与 NOIPNOI培训,参与NOI 投题,深谙命题思路,授课经验丰富,更能够站在学生立场剖析问题。教研团队全程参与课程设计规划、备课、教案审核及参与授课,确保课程优质高效。

  金牌授课、全面提升算法实现能力、机房授课、全程答疑、与全国高手PK经验交流,根据每周答疑情况,开设网课,从而进一步确保学员参训成果。

本文链接:http://quangdungfc.net/dongtaiguihua/305.html