Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
375 lines (283 sloc) 12 KB
layout title date categories
post
背包问题 - 动态规划
2018-09-22 20:00:05 +0800
算法

In short

常见的背包问题:

  1. 0-1 背包
  2. 多重背包
  3. 完全背包
  4. 多维背包
  5. 塞满背包

笔试题常遇到背包问题,做了一个简单的调研,mark down here,方便未来查阅。

Main

其他的背包问题都是 0-1 背包的延伸,解题思路也是借鉴 0-1 背包,所以重点是弄清楚最简单的 0-1 背包解题思路。

以下的所有问题都通过动态规划解决,动态规划适用于以下问题:

  1. 问题能够分解为子问题
  2. 全局最优依赖于局部最优,每次求局部最优能够求得全局最优
  3. 解空间有重叠,能够通过存储局部解,减少冗余计算
  4. 局部解不会失效

例如通过动态规划求 Fibonacci 数列:

def fibonacci():
    mark = {1: 1, 2: 1}
    n = 1
    while True:
        if n in mark:
            ret = mark[n]
        else:
            ret = mark[n - 1] + mark[n - 2]
            mark[n] = ret
        yield ret
        n += 1

声明:下述代码采用 Go 编程语言,默认会将数据初始化为零值,比如整形数组会初始化为 0;创建动态数组没 Java 灵活,需 make 创建 slice,但不影响理解代码逻辑。

0-1 背包

题目描述:有 N 件物品,第 i 件物品的重量为 w[i],价值为 p[i],承重为 W 的背包,每件物品有且仅有一件,要求最大化背包中物品的价值。

对于每件物品都有两种选择(放进背包 or not),那么时间复杂度就是 O(2 ^ N),问题复杂度成指数级别增长,但在 O(2 ^ N) 中有很多重复的子结构,有优化空间。

定义函数:f(i, v) 为在背包承重为 v 的情况下,在 1 ~ i 物品中选择若干件,最大化背包中物品的价值。显然 f(N, W) 是本题的最终答案。

初始条件下,f(0, 0...W) = 0f(0...N, 0) = 0,显然,没有物品和背包容量为 0 的情况下,价值最大化是 0。

状态转移函数:

f(i, v) = max{
                f(i - 1, v),
                f(i - 1, v - w[i]) + p[i] if v >= w[i] else 0
            }

为什么状态转移方程是这样?

如果 w[i] <= v,物品都有两种选择,放入背包 or not。那怎么判断是否应该放入背包呢?答案是两种方案都尝试一下,比较两种方案价值,选择价值更大者,在状态转移函数中是通过查表而不是重复计算子结构。

func zeroOneKnapsack(w, p []int, N, W int) int {
    f := make([][]int, N+1)
    for i := 0; i <= N; i++ {
        f[i] = make([]int, W+1)
    }

    for i := 1; i <= N; i++ {
        for v := 1; v <= W; v++ {
            if w[i] > v {
                f[i][v] = f[i-1][v]
            } else {
                f[i][v] = max(f[i-1][v], f[i-1][v-w[i-1]]+p[i-1])
            }
        }
    }

    return f[N][W]
}

例子:4 件物品,大小分别为 2, 3, 1, 2,价值分别为 4, 3, 5, 2,背包容量为 7。

按照上述代码,需要构造一个表格,然后按照规律填写表格:

初始状态下表格是这样的:

0 1 2 3 4 5 6 7
0 0 0 0 0 0 0 0 0
1 0
2 0
3 0
4 0

填写后:

0 1 2 3 4 5 6 7
0 0 0 0 0 0 0 0 0
1 0 0 4 4 4 4 4 4
2 0 0 4 4 4 7 7 7
3 0 5 5 9 9 9 12 12
4 0 5 5 9 9 9 12 12

最终返回 12。

使用动态规划复杂度是 O(N * W),通过存储解记录,下次需要时查表,减少冗余计算。在没有存储解记录的情况下,不难发现上述算法遍历 O(2 ^ N) 的解空间,把所有可能都已经纳入考虑了,得到的自然是最优解。动态规划聪明的地方不是将解空间有效缩小,而是存储解记录减少冗余计算。有兴趣的读者可以一步一步试着推导。

数组空间缩小为 O(W)

根据状态转移函数:

f(i, v) = max{
                f(i - 1, v),
                f(i - 1, v - w[i]) + p[i] if v >= w[i] else 0
            }

f(i, v) 只依赖于 f(i - 1, v)f(i - 1, v - w[i]) 两个解,也就是求解 f(i, 0...W) 只需要依赖于 f(i - 1, 0...W),可把存储空间降到 O(N)

func zeroOneKnapsackSpaceAdvance(w, p []int, N, W int) int {
    f := make([]int, W+1)
    for i := 1; i <= N; i++ {
        for v := W; v > 0 && w[i] <= v; v-- {
            // f(i, v) = max{ f(i - 1, v), f(i - 1, v - w[i]) + p[i]}
            f[v] = max(f[v-w[i]]+p[i], f[v])
        }
    }
    return f[W]
}

计算 f(i, v) 是从 W ==> 0 计算的,而不能是 0 ==> W。因为 f(i, v) 需要依赖 f(i - 1, v - w[i]),如果是从 0 ==> W 计算,有可能覆盖了 f(i - 1, v - w[i]) 从而丢失解记录。


多重背包

题目描述:有 N 件物品,第 i 件物品的重量为 w[i],价值为 p[i],数量为 n[i],背包承重为 W,要求最大化背包中物品的价值。

与 0-1 背包的区别:

在 0-1 背包,第 i 件物品只有两个选择,放入 or not。而多重背包,第 i 件物品可选择放入 0 ~ n[i] 件。

多重背包可以转化为 0-1 背包解决,将第 i 件物品,看成是 n[i] 件独立的,重量和价值等价的商品,可以直接复用 0-1 背包。

不把多重背包问题直接转化为 0-1 背包问题,拟定一个多重背包的状态转移函数:

f(i, v) = max(f(i - 1, v - k * w[i]) for k := 0...n[i] if v >= k * w[i])
func multiKnapsack(w, p, n []int, N, W int) int {
    f := make([][]int, N+1)
    for i := 0; i <= N; i++ {
        f[i] = make([]int, W+1)
    }
    for i := 1; i <= N; i++ {
        for v := 1; v <= W; v++ {
            for k := 0; k <= n[i]; k++ {
                if v >= k*w[i] {
                    f[i][v] = max(f[i-1][v], f[i-1][v-k*w[i]]+k*p[i])
                } else {
                    f[i][v] = f[i - 1][v]
                }
            }
        }
    }
    return f[N][W]
}

同样可以将空间复杂度降到 O(W)。

func multiKnapsackSpaceAdvance(w, p, n []int, N, W int) int {
    f := make([]int, W + 1)
    for i := 0; i <= N; i++ {
        for v := W; v > 0; v-- {
            for k := 1; k <= n[i] && v >= k * w[i]; k++ {
                f[v] = max(f[v], f[v - k * w[i]] + k * p[i])
            }
        }
    }
    return f[W]
}

完全背包

问题描述:有 N 件物品,每件物品数量有无数多个,第 i 件物品的重量为 w[i],价值为 p[i],背包承重为 W,要求最大化背包中物品的价值。

与多重背包有什么关联?

虽然物品的数量无上限,但是因为背包承重上限为 W,那么第 i 件商品最多只能够携带 W / w[i] 件,也就是完全背包可以转化为多重背包求解。只需要计算出每件物品的上限数量 n[i] = W / w[i] 就可以复用多重背包求解。

另一种方法是将有限资源(背包承重)的循环条件往外移动,确保背包的承重从小到大变化过程中保持局部最优解。

func comleteKnapsack(w, p []int, N, W int) int {
    f := make([]int, W+1)
    for v := 1; v <= W; v++ {
        for i := range w {
            if v >= w[i] {
                f[v] = max(f[v], f[v-w[i]]+p[i])
            }
        }
    }
    return f[W]
}

Leetcode 322. Coin Change

Leetcode 377. Combination Sum IV


多维背包

问题描述:有 N 件物品,每件物品数量为 1,第 i 件物品的重量为 w[i],大小为 s[i],价值为 p[i],背包承重为 W,容量为 S,要求最大化背包中物品的价值。

与 0-1 背包有什么关联?

物品属性的维度不再是单一的,除了重量还有大小,但动态规划的思路是一样的:探索整个解空间,并且存储解记录。

定义函数:f(i, v, y) 为在背包承重为 v,容量为 y 的情况下,在 1 ~ i 物品中选择若干件,最大化背包中物品价值。

状态转移函数:

f(i, v, y) = max {
                f(i - 1, v, y),
                f(i - 1, v - w[i], y - s[i]) if v >= w[i] and y >= s[i] else 0
            }

因为状态转移函数有三个变量,所以解空间大小为三维,需要一个三维数组存储解记录。

func multiDimensionKnapsack(w, p, s []int, N, W, S int) int {
    f := make([][][]int, N+1)
    for i := 0; i <= N; i++ {
        f[i] = make([][]int, W+1)
        for j := 0; j <= S; j++ {
            f[i][j] = make([]int, S+1)
        }
    }
    for i := 1; i <= N; i++ {
        for v := 0; v <= W; v++ {
            for y := 0; y <= S; y++ {
                if v >= w[i] && y >= s[i] {
                    f[i][v][y] = max(f[i-1][v][y], f[i-1][v-w[i]][y-s[i]])
                } else {
                    f[i][v][y] = f[i-1][v][y]
                }
            }
        }
    }
    return f[N][W][S]
}

同样的,存储空间可做降维。

func multiDimensionKnapsackSpaceAdvance(w, p, s []int, N, W, S int) int {
    f := make([][]int, W+1)
    for i := 0; i <= W; i++ {
        f[i] = make([]int, S+1)
    }
    for i := 1; i <= N; i++ {
        for v := W; v > 0 && v >= w[i]; v-- {
            for y := S; y > 0 && y >= s[i]; y-- {
                f[v][y] = max(f[v][y], f[v-w[i]][y-s[i]]+p[i])
            }
        }
    }
    return f[W][S]
}

Leetcode 474. Ones and Zeroes


塞满背包

题目描述:有 N 件物品,第 i 件物品大小为 w[i],背包容量为 W,问是否存在一种方案刚好塞满背包。

相似的问题:给出一个只有正数的数组 nums 和一个特定值 target,问 nums 的子序列是否存在数字之和为 target。

解决方案:对数组 nums 进行排序,创建一个数组记录某个值是否可达,经过所有遍历后,判断是否能够达到某个值。

如果原来该顶点已经可达,那么 f(i) = true;如果新发现能够到达 i 的路径,那么 f(i) = f(i - v)。

状态转移函数:

f(i) = f(i) || f(i - v)
func fullKnapsack(w []int, N, W int) bool {
    // f mark every value is reachable or not.
    f := make([]bool, W+1)
    // 0 can be reach always
    f[0] = true
    // make sure every number will be used just once.
    for _, v := range w {
        // loop from W to 0
        // if loop from 0 to W, every f[k * v] will be set true.
        for t := W; t > 0 && t >= v; t-- {
            f[t] = f[t] || f[t-v]
        }
    }
    // judge
    return f[W]
}

因为加法符合交换律,所以不需要对数组进行排序

dp 的值除了可以记录是否可达(true / false)外,还能够记录到达该顶点的路径数。

到达该值的方法 = 新发现路径数量 + 旧路径数量

状态转移函数:

f(i) = f(i) + f(i - v)
func knapsackWaysCnt(w []int, N, W int) int {
    f := make([]int, W+1)
    f[0] = 1
    for _, v := range w {
        for t := W; t >= v; t-- {
            f[t] += f[t-v]
        }
    }
    return f[W]
}

Leetcode 416. Partition Equal Subset Sum

Leetcode 494. Target Sum

Leetcode 139. Word Break

End

上述四种背包问题都采用动态规划解决,所有方案都没有效地缩小解空间,而是通过存储解记录,减少冗余计算。如果分析上述方案,会发现动态规划遍历整个解空间。

不足:如果物品的重量为浮点数,无法采用本博文方法解决。可复用动态规划思路,将浮点数转化为整数处理,但存储空间会被放大。