动态规划中的背包问题

Posted 2024-11-11 Updated 2024-12- 8

By Ray Lyu

19~25 min read

1. 概述

1.1. 动态规划

动态规划通过把原问题分解为相对简单的子问题来求解复杂的问题。因此，动态规划与分治法相似，区别在于动态规划的子问题会有重叠，而分治法的子问题是互不相交的。动态规划问题可以自底向上求解，也可以带备忘地自顶向下求解。二者的时间复杂度相同，但由于没有递归的开销，自底向上方式通常具有更小的系数。

1.2. 背包问题

根据维基百科 [2]，背包问题是 NP 完全问题（NP & NP Hard）。虽然该问题是 NP 完全的，但在实际应用中，可以通过包括动态规划在内的一些算法解决部分小规模的背包问题。

2. 经典背包问题

2.1. 01 背包

一共有 N 件物品，第 i 件物品的体积为 v[i]，价值为 c[i]。背包容纳的体积上限为 V，求背包能装入的物品的最大价值是多少？

定义 dp[i][j] 表示：将前 i 件物品放进容量为 j 的背包中可以获得的最大价值。这个状态，或者说最优解 dp[i][j]，可以分下面两种情形：

如果最优解中不含第 i 件物品，则 dp[i][j] = dp[i-1][j]
如果最优解中含有第 i 件物品，则 dp[i][j] = dp[i-1][j-v[i]] + c[i]

因此，必定有 dp[i][j] = max{dp[i-1][j], dp[i-1][j-v[i]] + c[i]}，称为该问题的状态转移方程。我们可以采用自底向上方式来求解，时间复杂度为O(NV)。

Leetcode 474 是 01 背包问题的一个扩展，将资源由一维扩展为了二维。

2.2. 完全背包（无界背包）

有 N 种物品和一个容量为 V 的背包，每种物品都有无限件可用。第 i 种物品的体积是 v[i] ，价值是 c[i] 。现在请你选取一些物品装入背包，使这些物品的体积总和不超过背包容量，且价值总和最大。（详参 OJ）

完全背包问题与 01 背包问题唯一的不同就是物品的数量变成了无限多个。此时状态变量的定义可以保持不变，但是需要修改状态转移方程，时间复杂度仍然为O(NV)

如果不选择第 i 种物品，dp[i][j] = dp[i-1][j]
如果选择第 i 种物品，dp[i][j] = dp[i][j-v[i]] + c[i]（这里是唯一的不同）

2.3. 多重背包（有界背包）

有 N 种物品和一个容量为 V 的背包。第 i 种物品最多有 s[i] 件，每件体积是 v[i]，价值是 c[i]。求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。（详参 OJ）

相对于完全背包，多重背包限制每种物品的数量为有限多个。此时状态 dp[i][j] 不再只由两种情况转移而来。

如果最优解不包含第 i 种物品，则 dp[i][j] = dp[i-1][j]
如果最优解包含第 i 种物品 1 件，则 dp[i][j] = dp[i-1][j-v[i]] + c[i]
……
如果最优解包含第 i 种物品 amount[i] 件，则 dp[i][j] = dp[i-1][j-v[i]*amount[i]] + c[i]*amount[i]

时间复杂度为 O(V*TotalAmount)。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, V;
    cin >> N >> V;
    
    vector<int> volume(N + 1);
    vector<int> value(N + 1);
    vector<int> amount(N + 1);
    for (int i = 1; i <= N; ++i) {
        cin >> volume[i] >> value[i] >> amount[i];
    }

    int dp[N+1][V+1];
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= V; ++j) {
            if (j < volume[i]) {
                dp[i][j] = dp[i-1][j];
            } else {
                dp[i][j] = dp[i-1][j];
                for (int k = 1; k <= amount[i]; ++k) {
                    if (j < k*volume[i]) {
                        break;
                    }
                    int tmp = dp[i-1][j - k*volume[i]] + k*value[i];
                    if (tmp > dp[i][j]) {
                        dp[i][j] = tmp;
                    }
                }
            }
        }
    }

    cout << dp[N][V] << endl;
}

3. 其它变形

3.1. 恰好装满

Leetcode 416（分割等和子集）：给你一个只含正整数的非空数组，请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

dp[i][j] 表示前 i 个元素能否选出和为 j 的集合，状态转移方程如下，

如果 j < nums[i-1]，dp[i][j] = dp[i-1][j]
否则，如果 j == nums[i-1]，dp[i][j] = true
否则，dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]]

func canPartition(nums []int) bool {
    sum := 0
    for _, m := range nums {
        sum += m
    }
    if sum % 2 != 0 {
        return false
    }

    target := sum / 2
    size := len(nums)
    dp := make([][]bool, size + 1)
    for i := 0; i < len(dp); i++ {
        dp[i] = make([]bool, target + 1)
    }

    dp[0][0] = true
    for i := 1; i <= size; i++ {
        for j := 1; j <= target; j++ {
            if nums[i-1] > j {
                dp[i][j] = dp[i-1][j]
                continue
            }
            if nums[i-1] == j {
                dp[i][j] = true
                continue
            }
            dp[i][j] = dp[i-1][j-nums[i-1]] || dp[i-1][j]
        }
    }

    return dp[size][target]
}

3.2. 用最少的物品恰好装满

Leetcode 322（零钱兑换）：给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。你可以认为每种硬币的数量是无限的。

func coinChange(coins []int, amount int) int {
    size := len(coins)
    dp := make([][]int, size + 1)
    for i := 0; i < len(dp); i++ {
        dp[i] = make([]int, amount + 1)
    }

    for j := 1; j <= amount; j++ {
        dp[0][j] = -1
    }

    for i := 1; i <= size; i++ {
        for j := 1; j <= amount; j++ {
            if j < coins[i-1] {
                dp[i][j] = dp[i-1][j]
                continue
            }
            if j == coins[i-1] {
                dp[i][j] = 1
                continue
            }
            if dp[i][j-coins[i-1]] != -1 && dp[i-1][j] != -1 {
                dp[i][j] = min(dp[i][j-coins[i-1]] + 1, dp[i-1][j]) 
            } else if dp[i][j-coins[i-1]] == -1 && dp[i-1][j] != -1 {
                dp[i][j] = dp[i-1][j]
            } else if dp[i][j-coins[i-1]] != -1 && dp[i-1][j] == -1 {
                dp[i][j] = dp[i][j-coins[i-1]] + 1
            } else {
                dp[i][j] = -1
            } 
        }
    }

    return dp[size][amount]
}

3.3. 恰好装满的方案种数

Leetcode 494（目标和）：给你一个非负整数数组 nums 和一个整数 target。向数组中的每个整数前添加“+”或“-” ，然后串联起所有整数，可以构造一个表达式。例如，nums=[2, 1]，可以在 2 之前添加“+” ，在 1 之前添加“-” ，然后串联起来得到表达式“+2-1”。返回可以通过上述方法构造的、运算结果等于 target 的不同表达式的数目。

该问题的状态转移方程不难得出，但是对于数组下标的处理值得注意。

func findTargetSumWays(nums []int, target int) int {
    size := len(nums)
    sum := 0
    for _, m :=  range nums {
        sum += m
    }
    convert := func (a int) int {
        return a + sum
    }

    dp := make([][]int, size + 1)
    for i := range dp {
        dp[i] = make([]int, sum * 2 + 1)
    }
    dp[0][convert(0)] = 1

    for i := 1; i <= size; i++ {
        for j := -sum; j <= sum; j++ {
            if j + nums[i-1] <= sum {
                dp[i][convert(j)] += dp[i-1][convert(j + nums[i-1])]
            }
            if j - nums[i-1] >= -sum {
                dp[i][convert(j)] += dp[i-1][convert(j - nums[i-1])]
            }
        }
    }

    if target > sum || target < -sum {
        return 0
    }
    return dp[size][convert(target)]
}

4. 参考资料

《算法导论》
https://en.wikipedia.org/wiki/Knapsack_problem
https://zhuanlan.zhihu.com/p/93857890

算法与数据结构

算法

License: CC BY 4.0