• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

夜深人静写算法(十五)- 完全背包

互联网 diligentman 1周前 (02-19) 12次浏览

文章目录

  • 一、前言
  • 二、完全背包问题
    • 1、状态设计
    • 2、状态转移方程
    • 3、对比 0/1 背包问题
    • 4、时间复杂度分析
  • 三、完全背包问题的优化
    • 1、时间复杂度优化
    • 2、空间复杂度优化
    • 3、优化后的代码实现
      • 1)0/1 背包
      • 2)完全背包
  • 四、完全背包问题的应用
    • 1、组合问题
    • 2、前缀最值优化
    • 3、总个数限制的完全背包
  • 五、完全背包问题相关题集整理

一、前言

  上一章讲解了 0/1 背包问题的应用和一些优化思路,如果能够全部理解,也算是对动态规划有一个初步了解了。
  那么这一章,作者将更加深入地对背包问题进行扩展,利用完全背包问题引入动态规划的一些时间复杂度的优化思路,建议读者将两篇文章结合起来看,希望能对您学习动态规划有一定的帮助。
  当然,作者的这篇文章只是起到抛砖引玉的作用,也是反复研读了动态规划神作《背包九讲》后的产物,实际的动态规划问题千变万化,还是需要我们自己在学习过程中不断总结、加深理解,遇到问题才能触类旁通、举一反三。
夜深人静写算法(十五)- 完全背包

二、完全背包问题

【例题1】有

n

(

n

<

=

100

)

n(n <=100)

n(n<=100) 种物品和一个容量为

m

(

m

<

=

10000

)

m(m <= 10000)

m(m<=10000) 的背包。第

i

i

i 种物品的容量是

c

[

i

]

c[i]

c[i],价值是

w

[

i

]

w[i]

w[i]。现在需要选择一些物品放入背包,每种物品可以无限选择,并且总容量不能超过背包容量,求能够达到的物品的最大总价值。

  • 以上就是完全背包问题的完整描述,和 0/1 背包的区别就是每种物品可以无限选取,即文中红色字体标注的内容;

1、状态设计

  • 第一步:设计状态;
  • 状态

    (

    i

    ,

    j

    )

    (i, j)

    (i,j) 表示前

    i

    i

    i 种物品恰好放入容量为

    j

    j

    j 的背包

    (

    i

    [

    0

    ,

    n

    ]

    ,

    j

    [

    0

    ,

    m

    ]

    )

    (i in [0, n], j in [0, m])

    (i[0,n],j[0,m])

  • d

    p

    [

    i

    ]

    [

    j

    ]

    dp[i][j]

    dp[i][j] 表示状态

    (

    i

    ,

    j

    )

    (i, j)

    (i,j) 下该背包得到的最大价值,即前

    i

    i

    i 种物品(每种物品可以选择无限件)恰好放入容量为

    j

    j

    j 的背包所得到的最大总价值;

2、状态转移方程

  • 第二步:列出状态转移方程;

    d

    p

    [

    i

    ]

    [

    j

    ]

    =

    m

    a

    x

    (

    d

    p

    [

    i

    1

    ]

    [

    j

    c

    [

    i

    ]

    k

    ]

    +

    w

    [

    i

    ]

    k

    )

    dp[i][j] = max(dp[i-1][j – c[i]*k] + w[i]*k)

    dp[i][j]=max(dp[i1][jc[i]k]+w[i]k)

    (

    0

    <

    =

    k

    <

    =

    j

    c

    [

    i

    ]

    )

    (0 <= k <= frac {j} {c[i]})

    (0<=k<=c[i]j)

  • 因为每种物品有无限种可放置,将它归类为以下两种情况:
  • 1)不放:如果 “第

    i

    i

    i 种物品不放入容量为

    j

    j

    j 的背包”,那么问题转化成求 “前

    i

    1

    i-1

    i1 种物品放入容量为

    j

    j

    j 的背包” 的问题;由于不放,所以最大价值就等于 “前

    i

    1

    i-1

    i1 种物品放入容量为

    j

    j

    j 的背包” 的最大价值,对应状态转移方程中

    k

    =

    0

    k = 0

    k=0 的情况, 即

    d

    p

    [

    i

    1

    ]

    [

    j

    ]

    dp[i-1][j]

    dp[i1][j]

  • 2)放 k 个:如果 “第

    i

    i

    i 种物品放入容量为

    j

    j

    j 的背包”,那么问题转化成求 “前

    i

    1

    i-1

    i1 种物品放入容量为

    j

    c

    [

    i

    ]

    k

    j-c[i]*k

    jc[i]k 的背包” 的问题;那么此时最大价值就等于 “前

    i

    1

    i-1

    i1 种物品放入容量为

    j

    c

    [

    i

    ]

    k

    j-c[i]*k

    jc[i]k 的背包” 的最大价值 加上放入

    k

    k

    k 个第

    i

    i

    i 种物品的价值,即

    d

    p

    [

    i

    1

    ]

    [

    j

    c

    [

    i

    ]

    k

    ]

    +

    w

    [

    i

    ]

    k

    dp[i-1][j – c[i]*k] + w[i]*k

    dp[i1][jc[i]k]+w[i]k

  • 枚举所有满足条件的

    k

    k

    k 就是我们所求的 “前

    i

    i

    i 种物品恰好放入容量为

    j

    j

    j 的背包” 的最大价值了。

  • 注意:由于每件物品都可以无限选择,所以这里描述的时候都是用的 “种” 作为单位,即代表不同种类的物品。

3、对比 0/1 背包问题

  • 完全背包问题是 0/1 背包问题的扩展,区别就是它可以选择 取 0 件、取 1 件、取 2 件……取

    k

    k

    k 件,而 0/1 背包问题 只能取 0 件、取 1 件。如果从状态转移方程出发,我们可以把两个问题进行归纳统一,得到一个统一的状态转移方程如下:

    d

    p

    [

    i

    ]

    [

    j

    ]

    =

    m

    a

    x

    (

    d

    p

    [

    i

    1

    ]

    [

    j

    c

    [

    i

    ]

    k

    ]

    +

    w

    [

    i

    ]

    k

    )

    dp[i][j] = max(dp[i-1][j – c[i]*k] + w[i]*k)

    dp[i][j]=max(dp[i1][jc[i]k]+w[i]k)

  • 对于 0/1 背包问题,

    k

    k

    k 的取值为

    0

    ,

    1

    0,1

    0,1

  • 对于完全背包问题,

    k

    k

    k 的取值为

    0

    ,

    1

    ,

    2

    ,

    3

    ,

    .

    .

    .

    ,

    j

    /

    c

    [

    i

    ]

    0, 1, 2, 3, …, j / c[i]

    0,1,2,3,...,j/c[i]

4、时间复杂度分析

  • 对于

    n

    n

    n 种物品放入一个容量为

    m

    m

    m 的背包,状态数为

    O

    (

    n

    m

    )

    O(nm)

    O(nm),每次状态转移的消耗为

    O

    (

    k

    )

    O(k)

    O(k),所以整个状态转移的过程时间复杂度是大于

    O

    (

    n

    m

    )

    O(nm)

    O(nm) 的,那么实际是多少呢?

  • 考虑最坏情况下,即

    c

    [

    i

    ]

    =

    1

    c[i] = 1

    c[i]=1 时,那么要计算的

    d

    p

    [

    i

    ]

    [

    j

    ]

    dp[i][j]

    dp[i][j] 的转移数为

    j

    j

    j,总的状态转移次数就是

    m

    (

    m

    +

    1

    )

    2

    frac {m(m + 1)} {2}

    2m(m+1),所以整个算法的时间复杂度是

    O

    (

    n

    m

    2

    )

    O(nm^2)

    O(nm2) 的,也就是说状态转移均摊时间复杂度是

    O

    (

    m

    )

    O(m)

    O(m) 的。

  • 接下来一节会对完全背包问题的时间和空间复杂度进行优化。

三、完全背包问题的优化

1、时间复杂度优化

  • 我们把状态转移方程进行展开后得到如下的

    k

    +

    1

    k+1

    k+1 个式子:

    d

    p

    [

    i

    ]

    [

    j

    ]

    =

    m

    a

    x

    {

    d

    p

    [

    i

    1

    ]

    [

    j

    ]

    (

    1

    )

    d

    p

    [

    i

    1

    ]

    [

    j

    c

    [

    i

    ]

    ]

    +

    w

    [

    i

    ]

    (

    2

    )

    d

    p

    [

    i

    1

    ]

    [

    j

    c

    [

    i

    ]

    2

    ]

    +

    w

    [

    i

    ]

    2

    (

    3

    )

    .

    .

    .

    d

    p

    [

    i

    1

    ]

    [

    j

    c

    [

    i

    ]

    k

    ]

    +

    w

    [

    i

    ]

    k

    (

    k

    +

    1

    )

    dp[i][j] = max begin{cases} dp[i-1][j] & (1)\ dp[i-1][j – c[i]] + w[i] & (2)\ dp[i-1][j – c[i]*2] + w[i]*2 & (3)\ … \ dp[i-1][j – c[i]*k] + w[i] *k & (k+1) end{cases}

    dp[i][j]=maxdp[i1][j]dp[i1][jc[i]]+w[i]dp[i1][jc[i]2]+w[i]2...dp[i1][jc[i]k]+w[i]k(1)(2)(3)(k+1)

  • 利用待定系数法,用

    j

    c

    [

    i

    ]

    j-c[i]

    jc[i] 代替上式的

    j

    j

    j 得到如下式子:

    d

    p

    [

    i

    ]

    [

    j

    c

    [

    i

    ]

    ]

    =

    m

    a

    x

    {

    d

    p

    [

    i

    1

    ]

    [

    j

    c

    [

    i

    ]

    ]

    (

    1

    )

    d

    p

    [

    i

    1

    ]

    [

    j

    c

    [

    i

    ]

    2

    ]

    +

    w

    [

    i

    ]

    (

    2

    )

    d

    p

    [

    i

    1

    ]

    [

    j

    c

    [

    i

    ]

    3

    ]

    +

    w

    [

    i

    ]

    2

    (

    3

    )

    .

    .

    .

    d

    p

    [

    i

    1

    ]

    [

    j

    c

    [

    i

    ]

    k

    ]

    +

    w

    [

    i

    ]

    (

    k

    1

    )

    (

    k

    )

    dp[i][j-c[i]] = max begin{cases} dp[i-1][j-c[i]] & (1)\ dp[i-1][j – c[i]*2] + w[i] & (2)\ dp[i-1][j – c[i]*3] + w[i]*2 & (3)\ … \ dp[i-1][j – c[i]*k] + w[i] *(k-1) & (k) end{cases}

    dp[i][jc[i]]=maxdp[i1][jc[i]]dp[i1][jc[i]2]+w[i]dp[i1][jc[i]3]+w[i]2...dp[i1][jc[i]k]+w[i](k1)(1)(2)(3)(k)

  • 等式两边都加上

    w

    [

    i

    ]

    w[i]

    w[i] 得到:

    d

    p

    [

    i

    ]

    [

    j

    c

    [

    i

    ]

    ]

    +

    w

    [

    i

    ]

    =

    m

    a

    x

    {

    d

    p

    [

    i

    1

    ]

    [

    j

    c

    [

    i

    ]

    ]

    +

    w

    [

    i

    ]

    (

    1

    )

    d

    p

    [

    i

    1

    ]

    [

    j

    c

    [

    i

    ]

    2

    ]

    +

    w

    [

    i

    ]

    2

    (

    2

    )

    d

    p

    [

    i

    1

    ]

    [

    j

    c

    [

    i

    ]

    3

    ]

    +

    w

    [

    i

    ]

    3

    (

    3

    )

    .

    .

    .

    d

    p

    [

    i

    1

    ]

    [

    j

    c

    [

    i

    ]

    k

    ]

    +

    w

    [

    i

    ]

    k

    (

    k

    )

    dp[i][j-c[i]] + w[i] = max begin{cases} dp[i-1][j-c[i]] + w[i] & (1)\ dp[i-1][j – c[i]*2] + w[i]*2 & (2)\ dp[i-1][j – c[i]*3] + w[i]*3 & (3)\ … \ dp[i-1][j – c[i]*k] + w[i] *k & (k) end{cases}

    dp[i][jc[i]]+w[i]=maxdp[i1][jc[i]]+w[i]dp[i1][jc[i]2]+w[i]2dp[i1][jc[i]3]+w[i]3...dp[i1][jc[i]k]+w[i]k(1)(2)(3)(k)

  • 于是我们发现,这里的

    (

    1

    )

    .

    .

    .

    (

    k

    )

    (1)…(k)

    (1)...(k) 式子等价于最开始的状态转移方程中的

    (

    2

    )

    .

    .

    .

    (

    k

    +

    1

    )

    (2) … (k+1)

    (2)...(k+1) 式,所以原状态转移方程可以简化为:

    d

    p

    [

    i

    ]

    [

    j

    ]

    =

    m

    a

    x

    (

    d

    p

    [

    i

    1

    ]

    [

    j

    ]

    ,

    d

    p

    [

    i

    ]

    [

    j

    c

    [

    i

    ]

    ]

    +

    w

    [

    i

    ]

    )

    dp[i][j] = max(dp[i-1][j], dp[i][j-c[i]] + w[i])

    dp[i][j]=max(dp[i1][j],dp[i][jc[i]]+w[i])

  • 这样就把原本均摊时间复杂度为

    O

    (

    m

    )

    O(m)

    O(m) 的状态转移优化到了

    O

    (

    1

    )

    O(1)

    O(1)

  • 那么我们来理解一下这个状态转移方程的含义:
  • 对于第

    i

    i

    i 种物品,其实只有两种选择:一个都不放、至少放一个;一个都不放 就是 “前

    i

    1

    i-1

    i1 种物品放满一个容量为

    j

    j

    j 的背包” 的情况,即

    d

    p

    [

    i

    1

    ]

    [

    j

    ]

    dp[i-1][j]

    dp[i1][j];至少放一个 的话,我们尝试在 “前

    i

    i

    i 种物品放满一个容量为

    j

    j

    j 的背包” 里拿掉 1 个物品,即 “前

    i

    i

    i 种物品放满一个容量为

    j

    c

    [

    i

    ]

    j-c[i]

    jc[i] 的背包”,这时候的值就是

    d

    p

    [

    i

    ]

    [

    j

    c

    [

    i

    ]

    ]

    +

    w

    [

    i

    ]

    dp[i][j-c[i]] + w[i]

    dp[i][jc[i]]+w[i]。取两者的大者就是答案了。

  • 其实这个思路我可以在本文开头就讲,也容易理解,之所以引入优化以及逐步推导的过程,就是想告诉读者,很多动态规划的问题是不能套用模板的,从简单的思路出发,加上一些推导和优化,逐步把复杂的问题循序渐进的求出来,才是解决问题的普遍思路。

2、空间复杂度优化

  • 根据最新推导得到的状态转移方程,利用上一章 0/1 背包中提到的滚动数组,同样可以适用于 完全背包。
  • 因为当前行的状态的值只依赖于上一行和当前行的状态,和上上一行、上上上一行的状态无关,所以可以利用滚动数组记录上一行和当前行的状态,将上一行和当前行的状态进行滚动计算(滚动数组的实现可以在上一章中找到,这里不再累述)。
  • 根据优化后的状态转移方程,我们发现状态转移的过程如图三-2-1所示:
    夜深人静写算法(十五)- 完全背包

    图三-2-1
  • 蓝色的格子代表的是已经计算出来的状态;红色的格子代表的是当前正在计算的状态,即

    d

    p

    [

    i

    ]

    [

    j

    ]

    dp[i][j]

    dp[i][j],它的值来自

    d

    p

    [

    i

    1

    ]

    [

    j

    ]

    dp[i-1][j]

    dp[i1][j]

    d

    p

    [

    i

    ]

    [

    j

    c

    [

    i

    ]

    ]

    dp[i][j-c[i]]

    dp[i][jc[i]],这两个值对应的格子一定是蓝色的;灰色的格子代表尚未进行计算的状态;

  • 为了将问题描述的更加清晰,我们把

    (

    i

    ,

    j

    )

    (i, j)

    (i,j) 看成是 二维笛卡尔坐标系上的点,

    i

    i

    i

    x

    x

    x 轴上,

    j

    j

    j

    y

    y

    y 轴上,如图三-2-2所示:
    夜深人静写算法(十五)- 完全背包


    图三-2-2
  • 任何一个状态在计算出来以后,只会给

    x

    x

    x 坐标比它大 或者

    y

    y

    y 坐标比它大 的使用,所以我们只需要保留一行状态,并且按照

    x

    x

    x 递增进行顺序计算,就可以做到把二维的问题转换成一维,将状态转移方程变成如下表示:

    d

    p

    [

    j

    ]

    =

    m

    a

    x

    (

    d

    p

    [

    j

    ]

    ,

    d

    p

    [

    j

    c

    [

    i

    ]

    ]

    +

    w

    [

    i

    ]

    )

    dp[j] = max(dp[j], dp[j-c[i]] + w[i])

    dp[j]=max(dp[j],dp[jc[i]]+w[i])

  • 这时我们发现,这个就是 0/1 背包在降维后的状态转移方程。
  • 最后给出 0/1 背包 和 完全背包 的状态转移代码的对比。

3、优化后的代码实现

1)0/1 背包

  • 求解状态数组时,按照容量大小逆序求解。
void zeroOneKnapsack(int knapsackSize, Knapsack *knap, int maxCapacity) {
    zeroOneKnapsackInit(maxCapacity);
    for(int i = 0; i < knapsackSize; ++i) {
        for(int j = maxCapacity; j >= knap[i].capacity; --j) {
            dp[j] = opt(dp[j], dp[j - knap[i].capacity] + knap[i].weight);
        }
    }
}

2)完全背包

  • 求解状态数组时,按照容量大小顺序求解。
void completeKnapsack(int knapsackSize, Knapsack *knap, int maxCapacity) {
    completeKnapsackInit(maxCapacity);
    for(int i = 0; i < knapsackSize; ++i) {
        for(int j = knap[i].capacity; j <= maxCapacity; ++j) {
            dp[j] = opt(dp[j], dp[j - knap[i].capacity] + knap[i].weight);
        }
    }
}

四、完全背包问题的应用

1、组合问题

【例题2】给定

n

(

n

<

10

)

n(n < 10)

n(n<10) 种面额的货币,第

i

i

i 种货币的价值为

a

[

i

]

a[i]

a[i],求组合出价值为

m

(

m

<

=

100000

)

m(m <= 100000)

m(m<=100000) 的方案数

m

o

d

mod

mod 100000007 。

  • 这里的

    a

    [

    i

    ]

    a[i]

    a[i] 可以看成是背包物品的容量,用

    d

    p

    [

    i

    ]

    [

    j

    ]

    dp[i][j]

    dp[i][j] 表示 前

    i

    i

    i 种货币组合出价值为

    j

    j

    j 的方案数,则有状态转移方程:

    d

    p

    [

    i

    ]

    [

    j

    ]

    =

    d

    p

    [

    i

    1

    ]

    [

    j

    ]

    +

    d

    p

    [

    i

    ]

    [

    j

    a

    [

    i

    ]

    ]

    dp[i][j] = dp[i-1][j] + dp[i][j – a[i]]

    dp[i][j]=dp[i1][j]+dp[i][ja[i]]

  • d

    p

    [

    i

    1

    ]

    [

    j

    ]

    dp[i-1][j]

    dp[i1][j] 代表第

    i

    i

    i 种货币不选时的方案数;

  • d

    p

    [

    i

    ]

    [

    j

    a

    [

    i

    ]

    ]

    dp[i][j – a[i]]

    dp[i][ja[i]] 代表包含前

    i

    i

    i 种货币组合出

    j

    a

    [

    i

    ]

    j-a[i]

    ja[i] 的方案数;

  • 整个过程只涉及加法,所以可以边计算边取模,初始状态

    d

    p

    [

    0

    ]

    [

    0

    ]

    =

    1

    dp[0][0] = 1

    dp[0][0]=1,最终答案为

    d

    p

    [

    n

    ]

    [

    m

    ]

    dp[n][m]

    dp[n][m]

  • 这类组合问题还可以用 母函数 来求解,限于篇幅不在本章讲解,有兴趣的读者可以自行上网查资料学习。

2、前缀最值优化

【例题3】商店里有

n

(

n

<

=

1000

)

n(n <=1000)

n(n<=1000) 种商品,第

i

i

i 种商品的价格为

w

[

i

]

w[i]

w[i] 元,如果购买第

i

i

i 种商品

x

x

x 件,花费

w

[

i

]

x

w[i]*x

w[i]x 元,并且可以获得

a

[

i

]

x

+

b

[

i

]

a[i] * x + b[i]

a[i]x+b[i] 颗糖果,问给定

m

(

m

<

=

2000

)

m(m <= 2000)

m(m<=2000) 元钱,求能够获得的最多糖果数。

  • d

    p

    [

    i

    ]

    [

    j

    ]

    dp[i][j]

    dp[i][j] 表示 购买前

    i

    i

    i 种商品总价为

    j

    j

    j 元,得到的最大糖果数,则有状态转移方程如下:

    d

    p

    [

    i

    ]

    [

    j

    ]

    =

    m

    a

    x

    (

    d

    p

    [

    i

    1

    ]

    [

    j

    ]

    ,

    d

    p

    [

    i

    1

    ]

    [

    j

    w

    [

    i

    ]

    k

    ]

    +

    a

    [

    i

    ]

    k

    +

    b

    [

    i

    ]

    )

    dp[i][j] = max( dp[i-1][j], dp[i-1][j – w[i]*k] + a[i]*k + b[i])

    dp[i][j]=max(dp[i1][j],dp[i1][jw[i]k]+a[i]k+b[i])

    (

    1

    <

    =

    k

    <

    =

    j

    w

    [

    i

    ]

    )

    (1 <= k <= frac j {w[i]})

    (1<=k<=w[i]j)

  • 分别为第

    i

    i

    i 种商品不买、购买 1 件、2 件、3 件、…

    k

    k

    k 件的情况来进行状态转移;

  • 状态数目

    O

    (

    n

    m

    )

    O(nm)

    O(nm),状态转移的开销

    O

    (

    m

    )

    O(m)

    O(m),所以最坏时间复杂度为

    O

    (

    n

    m

    2

    )

    O(nm^2)

    O(nm2),需要想办法进行优化;

  • 我们将上述状态转移方程进行拆分,得到:

    {

    x

    d

    p

    [

    i

    ]

    [

    j

    ]

    =

    m

    a

    x

    (

    d

    p

    [

    i

    1

    ]

    [

    j

    w

    [

    i

    ]

    k

    ]

    +

    a

    [

    i

    ]

    k

    )

    (

    1

    )

    d

    p

    [

    i

    ]

    [

    j

    ]

    =

    m

    a

    x

    (

    d

    p

    [

    i

    1

    ]

    [

    j

    ]

    ,

    x

    d

    p

    [

    i

    ]

    [

    j

    ]

    +

    b

    [

    i

    ]

    )

    (

    2

    )

    begin{cases} xdp[i][j] &= max(dp[i-1][j – w[i]*k] + a[i]*k) & (1)\ dp[i][j] &= max(dp[i-1][j], xdp[i][j] + b[i]) & (2) end{cases}

    {xdp[i][j]dp[i][j]=max(dp[i1][jw[i]k]+a[i]k)=max(dp[i1][j],xdp[i][j]+b[i])(1)(2)

  • (

    1

    )

    (1)

    (1) 式中

    x

    d

    p

    [

    i

    ]

    [

    j

    ]

    xdp[i][j]

    xdp[i][j] 代表的是:前

    i

    i

    i 种商品中,第

    i

    i

    i 件商品至少选择一件购买,

    a

    [

    i

    ]

    a[i]

    a[i] 部分的最大糖果数;

  • (

    2

    )

    (2)

    (2) 式含义不变,只是状态转移的开销从

    O

    (

    m

    )

    O(m)

    O(m) 变成了

    O

    (

    1

    )

    O(1)

    O(1)

  • 参考完全背包对取

    k

    k

    k 个问题的简化,我们把

    (

    1

    )

    (1)

    (1) 作如下化简,得到:

    x

    d

    p

    [

    i

    ]

    [

    j

    ]

    =

    m

    a

    x

    (

    d

    p

    [

    i

    1

    ]

    [

    j

    w

    [

    i

    ]

    ]

    +

    a

    [

    i

    ]

    ,

    x

    d

    p

    [

    i

    ]

    [

    j

    w

    [

    i

    ]

    ]

    +

    a

    [

    i

    ]

    )

    xdp[i][j] = max(dp[i-1][j – w[i]] + a[i], xdp[i][j – w[i]] + a[i])

    xdp[i][j]=max(dp[i1][jw[i]]+a[i],xdp[i][jw[i]]+a[i])

  • 这样一来

    (

    1

    )

    (1)

    (1)

    (

    2

    )

    (2)

    (2) 状态转移的时间复杂度都降为

    O

    (

    1

    )

    O(1)

    O(1),整个算法时间复杂度为

    O

    (

    n

    m

    )

    O(nm)

    O(nm)

3、总个数限制的完全背包

【例题4】对于

n

(

n

<

=

2000

)

n(n <= 2000)

n(n<=2000) 个结点的树,给定

n

1

n-1

n1 个数字

f

(

d

)

(

1

<

=

d

<

n

)

f(d) (1 <= d < n)

f(d)(1<=d<n),其中

d

d

d 代表树上结点的度数,求构造一棵树使得

i

=

1

n

f

(

d

e

g

(

i

)

)

sum_{i=1}^{n} f( deg(i) )

i=1nf(deg(i)) 最大 (

d

e

g

(

i

)

deg(i)

deg(i) 代表 结点

i

i

i 的度数)。

  • 对于树来说,结点数为

    n

    n

    n,那么边数一定是

    n

    1

    n-1

    n1,一条边提供两个度,即度数总和为

    2

    n

    2

    2n-2

    2n2

  • 度数相同的结点看成是一类物品,对于度数为

    d

    e

    g

    (

    i

    )

    deg(i)

    deg(i) 的结点

    i

    i

    i

    d

    e

    g

    (

    i

    )

    deg(i)

    deg(i) 看成是物品容量,

    f

    (

    d

    e

    g

    (

    i

    )

    )

    f( deg(i) )

    f(deg(i)) 看成是物品价值,每个物品可以无限选择,但是总数量要正好为

    n

    n

    n,总度数要正好为

    2

    n

    2

    2n-2

    2n2,于是这就是一个总个数有限制的完全背包问题了。

  • 规定第

    i

    i

    i 种物品的容量(即 度数)为

    i

    i

    i,价值为

    f

    (

    i

    )

    f(i)

    f(i)

  • d

    p

    [

    i

    ]

    [

    j

    ]

    [

    k

    ]

    dp[i][j][k]

    dp[i][j][k] 代表 前

    i

    i

    i 种物品选择了

    j

    j

    j 个,组成容量为

    k

    k

    k 的背包的最大价值。则有状态转移方程:

    d

    p

    [

    i

    ]

    [

    j

    ]

    [

    k

    ]

    =

    m

    a

    x

    (

    d

    p

    [

    i

    1

    ]

    [

    j

    ]

    [

    k

    ]

    ,

    d

    p

    [

    i

    ]

    [

    j

    1

    ]

    [

    k

    i

    ]

    +

    f

    (

    i

    )

    )

    dp[i][j][k] = max( dp[i-1][j][k], dp[i][j-1][k-i] + f(i) )

    dp[i][j][k]=max(dp[i1][j][k],dp[i][j1][ki]+f(i))

  • 状态数

    O

    (

    n

    3

    )

    O(n^3)

    O(n3),状态转移为

    O

    (

    1

    )

    O(1)

    O(1),所以整个算法的时间复杂度为

    O

    (

    n

    3

    )

    O(n^3)

    O(n3),对于

    n

    n

    n 为 2000 的量级是不行的;

  • 考虑到这是一棵树,总度数是

    2

    n

    2

    2n-2

    2n2,因为树是连通图,所以每个结点至少有 1 个度,于是我们不考虑度为 1 的点,而是将

    n

    2

    n-2

    n2 个度分配给

    n

    n

    n 个结点,每个结点能够分配到的度数可以是

    0

    ,

    1

    ,

    2

    ,

    3…

    n

    2

    0,1,2,3…n-2

    0,1,2,3...n2,无论怎么分配都能够组成一棵完整的树。

  • 那么我们可以认为不同的度数的结点作为不同类的物品,度数作为背包容量,背包容量保证大于 0 ,所以度数为0的需要去掉,那么总共

    n

    2

    n-2

    n2 个物品,每个物品的容量为

    c

    [

    i

    ]

    =

    i

    c[i] = i

    c[i]=i,权值为

    w

    [

    i

    ]

    =

    f

    (

    i

    +

    1

    )

    f

    (

    1

    )

    w[i] = f(i+1)-f(1)

    w[i]=f(i+1)f(1)

    (

    i

    >

    0

    )

    (i > 0)

    (i>0)

    d

    p

    [

    i

    ]

    [

    j

    ]

    =

    m

    a

    x

    (

    d

    p

    [

    i

    1

    ]

    [

    j

    ]

    ,

    d

    p

    [

    i

    ]

    [

    j

    c

    [

    i

    ]

    ]

    +

    w

    [

    i

    ]

    )

    dp[i][j] = max(dp[i-1][j], dp[i][j – c[i] ] + w[i] )

    dp[i][j]=max(dp[i1][j],dp[i][jc[i]]+w[i])

  • 最后的答案为

    d

    p

    [

    n

    2

    ]

    [

    n

    2

    ]

    +

    n

    f

    (

    1

    )

    dp[n-2][n-2] + n * f(1)

    dp[n2][n2]+nf(1)

  • 以上就是本文关于完全背包 的所有内容。

本文所有示例代码均可在以下 github 上找到:github.com/WhereIsHeroFrom/Code_Templates


夜深人静写算法(十五)- 完全背包


五、完全背包问题相关题集整理

题目链接 难度 解析
HDU 1114 Piggy-Bank ★☆☆☆☆ 完全背包 裸题
HDU 4508 湫湫系列故事——减肥记I ★☆☆☆☆ 【例题1】完全背包 裸题
HDU 1248 寒冰王座 ★☆☆☆☆ 组合问题 / 母函数
HDU 1284 钱币兑换问题 ★☆☆☆☆ 组合问题 / 母函数
HDU 1398 Square Coins ★☆☆☆☆ 【例题2】组合问题 / 母函数
HDU 1681 Frobenius ★☆☆☆☆ 组合问题 / 母函数
PKU 2229 Sumsets ★★☆☆☆ 组合问题 / 母函数
PKU 3181 Dollar Dayz ★★☆☆☆ 组合问题 / 母函数 + 大数模拟
HDU 1963 Investment ★★☆☆☆ 容量范围 / 1000
HDU 2159 FATE ★★☆☆☆ 二维 完全背包
HDU 3244 Inviting Friends ★★☆☆☆ 二分答案 + 完全背包
HDU 3127 WHUgirls ★★☆☆☆ 二维 完全背包 / 记忆化搜索
HDU 5410 CRB and His Birthday ★★★☆☆ 【例题3】前缀最值优化
HDU 5534 Partial Tree ★★★★☆ 【例题4】个数限制的完全背包

程序员灯塔
转载请注明原文链接:夜深人静写算法(十五)- 完全背包
喜欢 (0)