柚子快报激活码778899分享：算法 动态规划-完全背包问题
文章目录
1. 问题1.1 建模1.2 动态规划算法1.2.1 子问题界定1.2.2 子问题计算顺序1.2.3 优化函数的递推方程1.2.3.1 递推方程1.2.3.2 该递推方程和投资问题递推方程的不同之处
1.2.4 标记函数1.2.5 实例1.2.5.1 求F~k~(y)表、i~k~(y)表1.2.5.2 追踪解1.2.5.2.1 追踪过程1.2.5.2.2 追踪算法
1.2.6 时间复杂度
1. 问题
1.1 建模
解是一个向量：
∑
i
=
1
n
\sum_{i=1}^n
∑i=1nvixi 约束条件：
∑
i
=
1
n
\sum_{i=1}^n
∑i=1nwixi <=b
把问题分个类就是如图
1.2 动态规划算法
1.2.1 子问题界定
设定两个参数k，y k：考虑对物品1，2，…，k的选择 y：背包总重量不超过y
那么我们该问题就是当 k = n，y = b时最好的解法
1.2.2 子问题计算顺序
先给出k，当k确定以后，y再由小到大增长
k = 1，2，…，n对于给定的k，y = 1，2，…，b
1.2.3 优化函数的递推方程
1.2.3.1 递推方程
设Fk(y)为：装前k种物品，总重不超过y，背包达到的最大价值
Fk(y) = max{Fk-1(y)，Fk(y-wk)+vk}
注意： max里面第二项写的不是Fk-1，而是Fk，max函数里面第二项其实是 对Fk(y)这个函数的递归 ，这个递推的范围是只挑一个第k种物品到全部都挑第k种物品分几种情况，分别为：
Fk(y) = max{Fk-1(y)，Fk(y - wk) + vk}Fk(y) = max{Fk-1(y)，Fk(y - wk) + vk} 只装1个第k种物品当 Fk(y-wk) = max{Fk-1(y-wk)，Fk(y - wk - wk) + vk} 时 Fk(y) = max{Fk-1(y)，Fk(y - wk) + vk} = max{Fk-1(y)，Fk(y - wk - wk) + vk + vk} 即装2个第k种物品装4个、5个…第k种物品以此类推 F0(y) = 0,0<=y<=bFk(0) = 0,0<=k<=nF1(y) =
⌊
y
/
w
1
⌋
\lfloor y/{w_1}\rfloor
⌊y/w1⌋v1Fk(y) =
−
∞
-\infty
−∞，y<0
当重量小于0的时候，令其最大价值为
−
∞
-\infty
−∞，若不为
−
∞
-\infty
−∞，比如说为0，那么在max里面比较的时候就有可能max中的第二项，不符合实际 （选择了超重的那一项）
1.2.3.2 该递推方程和投资问题递推方程的不同之处
递推方程1号
按照投资问题那种形式来写递推方程2号 第k种物品用xk个，然后…
递推方程1号的时间复杂度会更小
对1号递推方程分析
记得我们的顺序，对k从小到大，然后在k给定的时候，对y从小到大，所以1号递推方程max中的第一项已经被计算过的，可以直接查1号方程max中第二项虽然k一样，但是递归的时候，y的值会不断变小，比如一开始y = 5，递归一次y = 4，再递归变成 y = 3…，那么这些值也都是计算过的，可以直接查所以1号方程递归一次只需要找到max 第一项Fk-1(y) 、找到max第二项中的Fk(y - wk)，然后做一次加法（给Fk(y - wk)加上vk），然后再做一次比较就可以了，是常数阶别的 对2号递推方程分析
首先先回顾一下投资问题的递推方程 这里只涉及到2个维度：项目种数，每个项目的收益 相比之下，背包问题的2号递推方程 涉及到3个维度：物品种数，每个物品价值，每个物品重量 他们递推方程的不同之处在于Fk-1项里面一个直接减去xk，一个减去xkwk 所以要把背包问题和投资问题分为两个问题来讲分析递推方程，由于w这个维度的出现，至少递推方程里面要多一个对w的遍历，遍历次数至少与n是相关的，所以时间复杂度较对号递推方程高
1.2.4 标记函数
设标记函数为ik(y)：装前k种物品。总重不超过y，背包达到最大价值时装入物品的最大标号
最大标号的意思是，比如此时在背包里面，你选的只有1号物品，2号物品，5号物品，那么最大标号就是5
没有选第k种物品的时候，最大标号就等于装前k-1种物品，重量仍不超过y的最大标号当选第k种物品的时候，最大标号就是k当只考虑第1种物品的时候，对应方程写在第二行
为什么要考虑“只考虑第1种物品”的时候呢？ 通过ik(y)的方程我们可以发现，ik(y)是跟着Fk(y)一起递归的，那么函数参数y的值就有可能变的非常小，我们要考虑递归的出口，所以要考虑
1.2.5 实例
1.2.5.1 求Fk(y)表、ik(y)表
方程写到这里方便看 先k = 1，y从小到大 然后k = 2，y从小到大…
求F1(1) F1(1) =
⌊
1
/
2
⌋
\lfloor 1/2 \rfloor
⌊1/2⌋×1 = 0求i1(1) i1(1) = 0 （当 k = 1的时候都用第二个图的第二行求的i）
求F1(2) F1(2) = max{F1-1(2)，F1(2-2) + 1} 即max{F0(2)，F1(0) + 1} = max{0，1} = 1求i1(2) i1(2) = 1 （同上）
求F1(3) F1(3) = max{F1-1(3)，F1(3-2) + 1} 即max{F0(3)，F1(1) + 1} = max{0，1} = 1求i1(3) i1(3) = 1 （同上） …
比如求F2(3) F2(3) = max{F2-1(3)，F2(3-3) + 3} 即max{F1(3)，F2(0) + 3} = max{1，3} = 3求i2(3) 因为Fk-1(y) = F1(3) = 1 Fk(y - wk) = F2(3 - 3) = F2(0) = 0 < Fk-1(y) 所以i2(3) = k =2 …
我们也可以看出来
求F的时候，虽然max中第二项是递归，但是每层递归都是已经被计算好的求i的时候，同样可以使用前面已经计算过的值
最终结果 F表
i表
1.2.5.2 追踪解
1.2.5.2.1 追踪过程
求in(b) 即i4(10) = 4 那么 x4 >= 1 原因：i的值等于4说明第4号物品被用过了，所以次数大于等于1，如果下一步求的 i 的值仍然为4，那么就说明第四号物品又被用了一遍，那么x4就应该大于等于2（不过这个例子中下一步求的 i 的值不是4，说明第四号物品只被用了一次）
y的值 y = 10 - w4 = 3 （第四号物品被用了一次，那么背包还剩下多少重量可以装？所以用10 - w4）这一步k的值仍为4 （除去上一步那个第四号物品，再考虑前4种物品中，背包重量为3的时候用的物品最大标号是多少呢） 所以这一步求的是 i4(3) = 2 那么 x2 >= 1，x4 = 1，x3 = 0 在上一步中，得出的结果是2，说明在刚刚的情况下，前4种物品中最大编号为2，说明这一步我们只考虑前2种物品就行了，然后y值同上一样减去1个第2种物品的重量 即 k = 2，y = 3 - w2 = 0 所以这一步求i2(0) = 0 那么x2 = 1，x1 = 0
综上，x1 = 0，x2 = 1，x3 = 0，x4 = 1，价值为12
1.2.5.2.2 追踪算法
注意： 这里算法只是追踪的算法，不是整个背包问题的算法 步骤详解： 1.先把所有种类的物品初值置为0 2.从最后开始追踪 3.在考虑前j种物品的时候，把物品的最大标号赋值给新的 j，为了方便描述我叫这个新赋值的j称为j新， （如此以来，下一次考虑的时候就是前j新 种物品了） 4.上一步的值为 j新，说明第 j新 种物品先装了1个，所以赋初值给 xj新 为 1 5.减去第 j新 种物品的重量 6.7.8. 如果最大物品编号仍然是j新，那么再减去第 j新 种物品的重量1次，并且说明这个物品又在背包里出现一次，xj新 = xj新+1 9.如果最大物品编号不是刚刚的 j新，并且不是 0 ，那么就回到步骤3，考查下一个 j
1.2.6 时间复杂度
备忘录里面一共有 nb 项 计算其中一个项的公式 需要常数时间（上面推算过，因为每一个项都可以在前面一点的备忘录里找到） 所以理论上来说时间复杂度为O(nb)
柚子快报激活码778899分享：算法 动态规划-完全背包问题
推荐链接
发表评论