14.5 背包问题

Kesa...大约 9 分钟

背包问题: 给定一组物品, 物品有价格和重量, 在限定重量的情况下, 如何选择使得物品的总价格最大.

0-1背包问题: 每种物品只有一个, 选择放入还是不放入.
有界背包问题(或多重背包问题): 每种物品是有限的
无界背包问题(或完全背包问题): 每种物品是无限的

14.5.1 问题101: 分割等和子集

给定一个非空的正整数数组 nums ，请判断能否将这些数字分成元素和相等的两部分。
示例 1：
输入：nums = [1,5,11,5]
输出：true
解释：nums 可以分割成 [1, 5, 5] 和 [11] 。
示例 2：
输入：nums = [1,2,3,5]
输出：false
解释：nums 不可以分为和相等的两部分
提示：
1 <= nums.length <= 200
1 <= nums[i] <= 100

14.5.1 分析&题解

将问题转化为, 对于数字和为sum/2的数组(背包), 能否将若干数字(物品)放满数组(背包), 每个数字只能用一次(0-1背包问题).

每次有两个选择, 放入还是不放入, 若需要得出所有结果用回溯法. 需要得出解的数量使用动态规划.

状态转移方程

假设 $f(i,j)$ 表示能否从[0,i-1]中选择数字放入容量为j的背包. 若数组大小为n, 背包容量为t, 那么 $f(n,t)$ 就是问题的解.

对于 $f(i,j)$ , 有两个选择:

放入数字nums[i-1], 若能从 [0, i-2] 中选择数字放满容量t-nums[i-1]背包, 即 $f(i-1, t-nums[i-1])$ , 那么 $f(i,j)=true$ 即 $f(i,j)= f(i-1, j-nums[i-1])$
不放入数字nums[i-1], $f(i,j)=f(i-1,j)$

初始值(最小问题解):

$f(i,0)$ : 背包容量为0, 只要不选择任何物品就行, 值为 T
$f(0,j), j>0$ : 没有数字放入背包, 不可能有解, 值为 F

迭代+二维数组

使用二维数组存放计算结果, dp[n-1][sum/2], 为解

func canPartition(nums []int) bool {
    n := len(nums)
    t := 0 // 背包容量
    for _, n := range nums {
        t += n
    }
    // 不能拆分
    if t % 2 == 1 {
        return false
    }

    t = t / 2
    
    // 缓存
    // dp[0][j], j in [1, t+1) 均为 F
    dp := make([][]bool, n+1)
    for i := range dp {
        dp[i] = make([]bool, t+1)
    }
    // 初始值
    for i := 0; i < n+1; i++ {
        dp[i][0] = true
    } 

    // 计算
    for i := 1; i < n+1; i++ {
        for j := 1; j < t+1; j++ {
            // 不放进背包
            dp[i][j] = dp[i-1][j]
            // 放进背包
            if !dp[i][j] && j >= nums[i-1] {
                dp[i][j] = dp[i-1][j-nums[i-1]]
            }
        }
    }

    return dp[n][t]
}

迭代+两行二维数组

计算只需要两行数据, 可减小二维数组大小到两行

func canPartition(nums []int) bool {
    n := len(nums)
    t := 0 // 背包容量
    for _, n := range nums {
        t += n
    }
    // 无法拆分
    if  t % 2 == 1 {
        return false
    }
    t = t / 2

    // 缓存
    dp := make([][]bool, 2)
    for i := range dp {
        dp[i] = make([]bool, t+1)
    }
    // 初始值
    dp[0][0] = true
    dp[1][0] = true

    // 计算
    for i := 1; i < n+1; i++ {
        for j := 1; j < t+1; j++ { 
            // 不放入
            dp[i%2][j] = dp[(i-1)%2][j]
            // 放入
            if !dp[i%2][j] && j >= nums[i-1] {
                dp[i%2][j] = dp[(i-1)%2][j-nums[i-1]]
            }
        }
    }

    return dp[n%2][t]
}

迭代+一维数组

计算 $f(i,j)$ 需要用到 $f(i-1, j-nums[i-1]), f(i-1,j)$

用dp[j]存储上一行的值 $f(i-1, j)$ ,dp[j-1]存储 $f(i-1, j-nums[i-1])$

计算dp[j+1]即 $f(i+1, j+nums[i])$ 需要dp[j]即 $f(i-1,j)$ 的值, 故计算之后不能直接替换dp[j].

从右往左计算的话, 使用玩 $f(i-1,j)$ 之后就不会被用到.

func canPartition(nums []int) bool {
    n := len(nums)
    t := 0 // 背包容量
    for _, n := range nums {
        t += n
    }
    // 无法拆分
    if t % 2 == 1 {
        return false
    }
    t = t / 2

    // 缓存
    dp := make([]bool, t+1) 
    dp[0] = true

    // 计算
    for i := 1; i < n+1; i++ {
        // 从右到左
        for j := t; j >= 1; j-- {
            // 放入背包
            // dp[j] = dp[j]
            // 不放入
            if  !dp[j] && j >= nums[i-1] {
                dp[j] = dp[j-nums[i-1]]
            }
        }
    }
    
    return dp[t]
}

14.5.2 问题102: 加减的目标值

LCR 102. 目标和open in new window

给定一个正整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
示例 1：
输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3
示例 2：
输入：nums = [1], target = 1
输出：1
提示：
1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000

14.5.2.1 分析&题解

假设表达式中, 添加+的数字之和为p, 添加-的数字之和为q, 则有目标值 $S=p-q$ . 假设所有的数字和为Sum, 则有

$Sum=p+q \implies Sum+S=2p \implies p=(S+Sum)/2$

此时问题就变成了0-1背包问题, 从数组中选择数字放入容量为(S+Sum)/2的背包中.

状态转移方程

假设 $f(i,j)$ 表示从[0,i-1]选择数字放入j容量的背包中的方法数量,那么最终解就是 $f(n, t)$ , n为数组长度, t为背包容量.

对于 $f(i,j)$ , 数字nums[i]:

$j<nums[i]$ $j < n u m s [i]$ :
- 不能放入, $f(i,j)=f(i-1,j)$
$j\ge nums[i]$ $j \geq n u m s [i]$
- 放入, 则 $f(i,j)=f(i-1,j-nums[i-1])$
- 不放入, 则 $f(i,j)=f(i-1,j)$

则 $f(i,j)=f(i-1,j-nums[i-1])+f(i-1,j)$

初始值(最小问题解):

$f(i,0)$ : 不放入背包即可, 方法数为 1
$f(0,j),j>0$ : 无法满足, 方法数为 0

综上, 状态转移方程:

$f(i,j)=\begin{cases} 1 & j=0 \\ 0 &i=0,j>0 \\ f(i-1,j) & j < nums[i-1]\\ f(i-1,j-nums[i-1])+f(i-1,j) & i>0,j\ge nums[i-1] \end{cases}$

迭代+一维数组

使用dp[j]存储 $f(i-1,j)$ 和 $f(i,j)$ 的内容, 又因为下次运算需要用到 $f(i-1,j)$ , 所以不能直接用计算后的结果替换.

需要从右到左计算, 这样计算完毕后 $f(i-1,j)$ 的内容将不会在使用, 放心替换.

func findTargetSumWays(nums []int, target int) int {
	n := len(nums)

	sum := 0 // 数组元素和
	for _, n := range nums {
		sum += n
	}

	// 不能拆分成两个背包
	// 或 所有数加起来都小于 target
	if (sum+target)%2 != 0 || sum < target {
		return 0
	}

	// 背包容量
	t := (sum + target) / 2

	// 缓存
	dp := make([]int, t+1)
	// 初始值(最小问题解)
	dp[0] = 1

	// 计算
	for i := 1; i < n+1; i++ {
		// 从右向左计算, 避免覆盖原数据
		for j := t; j >= nums[i-1]; j-- {
			dp[j] += dp[j-nums[i-1]]
		}
	}

	return dp[t]
}

注意: 从右向左计算的循环条件, for j := t; j >= nums[i-1]; j--

14.5.3 问题103: 最小的硬币数目

LCR 103. 零钱兑换open in new window

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1
示例 2：
输入：coins = [2], amount = 3
输出：-1
示例 3：
输入：coins = [1], amount = 0
输出：0
示例 4：
输入：coins = [1], amount = 1
输出：1
示例 5：
输入：coins = [1], amount = 2
输出：2
提示：
1 <= coins.length <= 12
1 <= coins[i] <= 2^31 - 1
0 <= amount <= 10^4

14.5.3.1 分析&题解

将硬币看作物品, 总金额看作背包容量, 那么问题等价于求将背包放满的最小件数. 因为硬币可以使用无限次, 不再是0-1背包问题, 而是无界背包问题.

状态转移方程

假设 $f(i)$ 为组成金额 $i$ 的最小硬币数, 那么要得到 $f(i)$ , 有n(硬币种类)种选择, 当选择硬币 $Coin[j]$ 时有 $f(i)=f(i-Coint[j])+1$ .

由于需要求最小硬币数, 那么需要得出所有情况的最小值, 最终状态转移方程为:

$f(i)=min_{0,1,2,...,n-1}(f(i-Coin[j]+1)), Coin[j]\le i$

$f(0)$ 为0, 表示金额为0时, 硬币数为0.

func coinChange(coins []int, amount int) int {
    // 缓存
    dp := make([]int, amount+1)
    for i := 1; i < amount+1; i++ {
        dp[i] = amount + 1 // 存放最小值
        for _, c := range coins {
            if i >= c {
                dp[i] = min(dp[i], dp[i-c]+1)
            }
        }
    }

    if dp[amount] > amount {
        return -1
    }

    return dp[amount]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

14.5.4 问题104: 排列的数目

LCR 104. 组合总和 Ⅳopen in new window

给定一个由不同正整数组成的数组 nums ，和一个目标整数 target 。请从 nums 中找出并返回总和为 target 的元素组合的个数。数组中的数字可以在一次排列中出现任意次，但是顺序不同的序列被视作不同的组合。
题目数据保证答案符合 32 位整数范围。
示例 1：
输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。
示例 2：
输入：nums = [9], target = 3
输出：0
提示：
1 <= nums.length <= 200
1 <= nums[i] <= 1000
nums 中的所有元素 互不相同
1 <= target <= 1000

14.5.5 分析&题解

状态转移方程

$f(i)=\sum f(i-nums[j]), nums[j]\le i$

$f(i)$ 表示和为 $i$ 的排列数, 问题的解为 $f(t)$ .

$f(0)=1$ , 只有空排列的和为0

func combinationSum4(nums []int, target int) int {
    dp := make([]int, target+1)
    dp[0] = 1
    
    for i := 1; i < target+1; i++ {
        for _, n := range nums {
            if i >= n {
                dp[i] += dp[i-n]
            } 
        }
    }

    return dp[target]
}

Reference

剑指Offer（专项突破版）open in new window

昵称

邮箱

网址

按正序
按倒序
按热度

14.5 背包问题

# 14.5.1 问题101: 分割等和子集

# 14.5.1 分析&题解

# 状态转移方程

# 迭代+二维数组

# 迭代+两行二维数组

# 迭代+一维数组

# 14.5.2 问题102: 加减的目标值

# 14.5.2.1 分析&题解

# 状态转移方程

# 迭代+一维数组

# 14.5.3 问题103: 最小的硬币数目

# 14.5.3.1 分析&题解

# 状态转移方程

# 14.5.4 问题104: 排列的数目

# 14.5.5 分析&题解

# 状态转移方程

# Reference

预览:

14.5.1 问题101: 分割等和子集

14.5.1 分析&题解

状态转移方程

迭代+二维数组

迭代+两行二维数组

迭代+一维数组

14.5.2 问题102: 加减的目标值

14.5.2.1 分析&题解

状态转移方程

迭代+一维数组

14.5.3 问题103: 最小的硬币数目

14.5.3.1 分析&题解

状态转移方程

14.5.4 问题104: 排列的数目

14.5.5 分析&题解

状态转移方程

Reference