动态规划-02完全背包

问题描述

有n个物品,它们有各自的体积和价值,现有给定容量V的背包,每种物品都就可以选择任意数量,如何让背包里装入的物品具有最大的价值总和?


这个问题类似于动态规划-01背包,所不同的在于每种物品无限件。也就是从每种物品的角度考虑,与它相关的策略已并非取或不取两种,而是有取0件、取1件、取2件……等很多种。

仍然按照解01背包时的思路,令f[i][j]表示前i种物品恰放入一个容量为V的背包的最大价值。
f(i,j)表示前i种物品放入一个容量为j的背包获得的最大价值,那么对于第i种物品,我们有k种选择,0 <= k * V[i] <= t,即可以选择0、1、2...k个第 i 种物品,所以递推表达式为:

仍然可以按照每种物品不同的策略找出递推关系,写出状态转移方程:

0 <= k * v[i] <= V: f(i,j) = Max{ f(i-1,j),f(i-1,j-vi *k) + vi * k }

递归解法:

  1. 简单暴力循环,嵌套一个关于k的循环,第 i 种物品可选数量 k ∈ [0,V/v[i]]
class Solution {
    
    // 体积
    let v:[Int] = [0,5,7]
    // 价格
    let p:[Int] = [0,5,8]
    func findMaxPrice(capital V: Int) -> Int {
        var dp = Array(repeating: Array(repeating: 0, count: V + 1), count: v.count)
        
        for i in 1..<v.count {
            for j in v[i]...capital {
                var k = 0
                while k * v[i] <= j {
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i] * k] + p[i] * k)
                    k += 1
                }
            }
        }
        return dp[v.count - 1][V]
    }
}

求解 f[i][j] 的时间是 O(V/v[i]),总的复杂度可以认为是 O(N∗Σ(V/v[i])),是比较大的。

  1. 转化为01背包问题再求解。既然01背包问题是最基本的背包问题,那么我们可以考虑把完全背包问题转化为01背包问题来解
  • 最简单的想法:考虑到第 i 种物品最多选 V/v[i] 件,于是可以把第 i 种物品转化为 V/v[i] 件费用及价值均不变的物品,然后求解这个01背包问题。这样完全没有改进基本思路的时间复杂度,但这毕竟给了我们将完全背包问题转化为01背包问题的思路:将一种物品拆成多件物品。
  • 更高效的转化方法是:二进制的思想,把第 i 种物品拆成费用为 v[i]∗2k,价值为 v[i]∗2k 的若干件物品,其中 k 满足v[i]∗2k<=V。因为不管最优策略选几件第 i 种物品,总可以表示成若干个2k件物品的和。这样把每种物品拆成O(log(V/v[i]))件物品,是一个很大的改进。
  1. 时间:O(VN),空间:O(V)的最优算法。01背包中用 j 逆序遍历(即 V -> 0 )的顺序实现了二维数组到一维数组的优化转化。
    类似的完全背包也可以进行非常相似的优化:
for (int i = 1; i <= n; i++)
    for (int j = v[i]; j <= V; j++)
        f[j] = max(f[j], f[j - v[i]] + p[i]);

这个代码与01背包的代码只有 j 的循环次序不同而已。
01背包中要按照 j=V...0 的逆序遍历。这是因为要保证第 i 次循环中的状态 f[i][j] 是由状态 f[i−1][j−v[i]] 递推而来。换句话说,这正是为了保证每件物品只选一次
完全背包的特点恰是每种物品可选无限件,所以在考虑“加选一件第 i 种物品”这种策略时,却正需要一个可能已选入第 i 种物品的子结果 f[i][j−v[i]],所以就可以并且必须采用 j=0...V的顺序循环。这就是这个简单的程序为何成立的道理。值得一提的是,上面的伪代码中两层for 循环的次序可以颠倒,这个结论有可能会带来算法时间常数上的优化。

完整的代码如下:

class Solution {
    
    // 体积
    let v:[Int] = [0,5,7]
    // 价格
    let p:[Int] = [0,5,8]
    func findMaxPrice(capital V: Int) -> Int {
        var dp = Array(repeating: 0, count: V + 1)
        
        for i in 1..<v.count {
            for j in v[i]...V {
               dp[j] = max(dp[j], dp[j - v[i]] + p[i])
            }
        }
        return dp[V]
    }
}

这里我们不再讲解递归解法,有兴趣可以自行尝试。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 199,340评论 5 467
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 83,762评论 2 376
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 146,329评论 0 329
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 53,678评论 1 270
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 62,583评论 5 359
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 47,995评论 1 275
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,493评论 3 390
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,145评论 0 254
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,293评论 1 294
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,250评论 2 317
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,267评论 1 328
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 32,973评论 3 316
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,556评论 3 303
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,648评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 30,873评论 1 255
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 42,257评论 2 345
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 41,809评论 2 339