055.01背包、有依赖的背包

前置知识：讲解067、讲解068 二维动态规划及其空间压缩技巧、堆（题目6 用）

本节课讲述 §

1. 01 背包：每个物品要和不要两种可能性展开
   • 题目1 ~ 题目4
2. 有依赖的背包：多个物品变成一个复合物品（互斥），每件复合物品不要和怎么要多种可能性展开
   • 互斥：一个物品只能存在于一个复合物品中
   • 题目5
3. 不能用 01 背包来解，但是非常重要的问题：非负数组前 k 个最小的子序列和问题
   • 题目6

复杂度 §

• 时间复杂度：$O(物品个数\ast 背包容量)$
• 额外空间复杂度：$O(背包容量)$

备注 §

三维动态规划 已经讲了多维费用背包问题

题目1.01 背包模版 §

题目描述 §

给定一个正数 t，表示背包的容量

有 m 个货物，每个货物可以选或不选，但最多只能选择一次

每个货物有自己的体积 costs[i] 和价值 values[i]

返回在不超过总容量的情况下，怎么挑选货物能达到价值最大，返回最大的价值

测试链接 §

P1048【NOIP2005 普及组】采药

思路 §

dp[i][j]：只对前 i 个（或者说第 1 ~ 第 i 个，共 i 个）物品进行选择，当背包容量为 j 时，可以装的最大价值

状态转移：

1. 不选第 i 件物品：就是在前 i-1 件物品中选，即 dp[i-1][j]
2. 选第 i 件物品：在前 i-1 件物品中选 + 选第 i 件物品，dp[i-1][j-costs[i]] + values[i]

位置依赖：每个格子依赖上（dp[i-1][j]）和左上某一个格子（dp[i-1][j-costs[i]]）

所以从上往下推，将第一行进行初始化即可

初始化：dp[0][*] 代表没有物品可选，最大价值应该都是 0

空间压缩：i 层只依赖 i-1 层左侧位置，滚动数组，从上往下、从右往左递推

答案 §

package main
 
import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)
 
const (
	MAXM = 101
	MAXT = 1001
)
 
var (
	t      int
	m      int
	costs  = [MAXM]int{}
	values = [MAXM]int{}
	dp     = [MAXT]int{}
)
 
func main() {
	// s := `70 3
	// 71 100
	// 69 1
	// 1 2`
	// in := bufio.NewScanner(strings.NewReader(s))
	in := bufio.NewScanner(os.Stdin)
	in.Split(bufio.ScanWords)
	out := bufio.NewWriterSize(os.Stdout, 4096)
	for in.Scan() {
		t, _ = strconv.Atoi(in.Text())
		in.Scan()
		m, _ = strconv.Atoi(in.Text())
		for i := 1; i <= m; i++ {
			in.Scan()
			costs[i], _ = strconv.Atoi(in.Text())
			in.Scan()
			values[i], _ = strconv.Atoi(in.Text())
		}
		fmt.Fprintln(out, compute())
	}
	out.Flush()
}
 
// 严格位置依赖的动态规划：略
 
// 空间压缩
func compute() int {
	for j := 0; j <= t; j++ {
		dp[j] = 0
	}
	for i := 1; i <= m; i++ {
		for j := t; j >= costs[i]; j-- {
			dp[j] = max(dp[j], dp[j-costs[i]]+values[i])
		}
	}
	return dp[t]
}

题目2.夏季特惠 §

题目描述 §

某公司游戏平台的夏季特惠开始了，你决定入手一些游戏。现在你一共有 X 元的预算，该平台上所有的 n 个游戏均有折扣

标号为 i 的游戏的原价 ai​ 元，现价只要 bi ​元（也就是说该游戏可以优惠 ai​−bi ​ 元）并且你购买该游戏能获得快乐值为 wi

由于优惠的存在，你可能做出一些冲动消费导致最终买游戏的总费用超过预算，但只要满足获得的总优惠金额不低于超过预算的总金额，那在心理上就不会觉得吃亏。

现在你希望在心理上不觉得吃亏的前提下，获得尽可能多的快乐值。

格式：

输入：
- 第一行包含两个数 n 和 X。
- 接下来 n 行包含每个游戏的信息，原价 ai，现价 bi，能获得的快乐值为 wi。
输出：
- 输出一个数字，表示你能获得的最大快乐值。

示例 1：

输入：
     4 100
     100 73 60
     100 89 35
     30 21 30
     10 8 10
输出：100
解释：买 1、3、4 三款游戏，获得总优惠 38 元，总金额 102 元超预算 2 元，满足条件，获得 100 快乐值。

示例 2：

输入：
     3 100
     100 100 60
     80 80 35
     21 21 30
输出：60
解释：只能买下第一个游戏，获得 60 的快乐值。

示例 3：

输入：
     2 100
     100 30 35
     140 140 100
输出：135
解释：两款游戏都买，第一款游戏获得优惠 70 元，总开销 170 元，超过预算 70 元，超出预算金额不大于获得优惠金额满足条件，因此可以获得最大快乐值为 135。

提示：

• 所有输入均为整型数
• 1 <= n <= 500
• 0 <= x <= 10^5
• 0 <= b_i <= a_i <= 500
• 1 <= w_i <= 10^9

测试链接 §

bytedance-006.夏季特惠

思路 §

每件物品的花费（心理上不觉得吃亏）变成了 现价 - (原价 - 现价)

1. 如果这个值 <= 0：说明优惠大于价格，那么一定要买。因为快乐值 > 0，买了会增加心理预期，直接加到本金上
2. 如果这个值 > 0：说明价格大于优惠，就要动态规划考虑是不是要买了

这样这个问题就转化成了标准的 01 背包问题了

答案 §

package main
 
import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)
 
const (
	MAXN = 501
	MAXX = 1e5 + 1
)
 
var (
	n      int
	x      int
	costs  = [MAXN]int{}
	values = [MAXN]int{}
	dp     = [MAXX]int{}
)
 
func main() {
	in := bufio.NewScanner(os.Stdin)
	in.Split(bufio.ScanWords)
	out := bufio.NewWriterSize(os.Stdout, 4096)
	for in.Scan() {
		n, _ = strconv.Atoi(in.Text())
		in.Scan()
		x, _ = strconv.Atoi(in.Text())
		ans := 0
		well := 0
		idx := 1
		pre, cur, happy := 0, 0, 0
		for i := 1; i <= n; i++ {
			// 原价
			in.Scan()
			pre, _ = strconv.Atoi(in.Text())
			// 现价
			in.Scan()
			cur, _ = strconv.Atoi(in.Text())
			// 快乐值
			in.Scan()
			happy, _ = strconv.Atoi(in.Text())
			// 心理预期值：价格 - 优惠
			well = cur - (pre - cur)
			if well <= 0 {
				// 优惠大于价格，一定要买
				// 加到本金上（心理上更不觉得吃亏）
				x += -well
				// 买了，快乐值加上
				ans += happy
			} else {
				// 价格大于优惠，动态规划考虑是不是要买
				costs[idx] = well
				values[idx] = happy
				idx++
			}
		}
		ans += compute()
		fmt.Fprintln(out, ans)
	}
	out.Flush()
}
 
// 标准 01 背包
func compute() int {
	for j := 0; j <= x; j++ {
		dp[j] = 0
	}
	for i := 1; i <= n; i++ {
		for j := x; j >= costs[i]; j-- {
			dp[j] = max(dp[j], dp[j-costs[i]]+values[i])
		}
	}
	return dp[x]
}
 
// go 版本太低，没有内置的 max 函数
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

题目3.目标和 §

题目描述 §

给你一个非负整数数组 nums 和一个整数 target。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

• 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

提示：

• 1 <= nums.length <= 20
• 0 <= nums[i] <= 1000
• 0 <= sum(nums[i]) <= 1000
• -1000 <= target <= 1000

测试链接 §

494.目标和

暴力递归 §

var (
	theNums   []int
	theTarget int
	n         int
)
 
func findTargetSumWays(nums []int, target int) int {
	theNums = nums
	theTarget = target
	n = len(nums)
	return f(0, 0)
}
 
// nums[0:i] 范围上，已经形成的累加和是 sum
// nums[i:] 范围上，每个数字可以标记 + 或者 -
// 最终形成累加和为 target 的不同表达式数目
func f(i, sum int) int {
	if i == n {
		if sum == theTarget {
			return 1
		}
		return 0
	}
 
	return f(i+1, sum+theNums[i]) + f(i+1, sum-theNums[i])
}

记忆化搜索 §

var (
	theNums   []int
	theTarget int
	n         int
	cache     map[int]map[int]int
)
 
func findTargetSumWays(nums []int, target int) int {
	theNums = nums
	theTarget = target
	n = len(nums)
	// 因为累加和可以为负数
	// 所以缓存动态规划表用哈希表
	cache = map[int]map[int]int{}
	return f(0, 0)
}
 
// nums[0:i] 范围上，已经形成的累加和是 sum
// nums[i:] 范围上，每个数字可以标记 + 或者 -
// 最终形成累加和为 target 的不同表达式数目
func f(i, sum int) int {
	if i == n {
		if sum == theTarget {
			return 1
		}
		return 0
	}
 
	a, has := cache[i]
	if !has {
		a = map[int]int{}
		cache[i] = a
	}
	b, has := a[sum]
	if has {
		return b
	}
 
	ans := f(i+1, sum+theNums[i]) + f(i+1, sum-theNums[i])
	a[sum] = ans
	return ans
}

位置依赖 §

原本的 dp[i][j] 含义：nums[:i] 范围上，已经形成的累加和是 sum，nums[i:] 范围上，每个数字可以标记 + 或者 -，最终形成累加和为 target 的不同表达式数目

平移技巧：因为 sum 可能为负数，为了下标不出现负数，原本的 dp[i][j] 由 dp 表中的 dp[i][j+s] 来表示

重要技巧：当 dp 有负数时，平移技巧！

每一层依赖上一层：初始化最上层，从上往下遍历

func findTargetSumWays(nums []int, target int) int {
	s := 0
	for _, num := range nums {
		s += num
	}
	if target < -s || target > s {
		return 0
	}
	n := len(nums)
	// -s~s => 2*s+1
	m := s<<1 + 1
	// 原本的 dp[i][j] 含义：
	// nums[:i] 范围上，已经形成的累加和是 sum
	// nums[i:] 范围上，每个数字可以标记 + 或者 -
	// 最终形成累加和为 target 的不同表达式数目
	// 平移技巧：
	// 因为 sum 可能为负数，为了下标不出现负数，
	// 原本的 dp[i][j] 由 dp 表中的 dp[i][j+s] 来表示
	dp := make([][]int, n+1)
	for i := range dp {
		dp[i] = make([]int, m)
	}
	// 初始化：dp[n][target] = 1
	dp[n][target+s] = 1
	// 每一层依赖上一层：从上往下遍历
	for i := n - 1; i >= 0; i-- {
		for j := -s; j <= s; j++ {
			if j+nums[i]+s < m {
				dp[i][j+s] = dp[i+1][j+nums[i]+s]
			}
			if j-nums[i]+s >= 0 {
				dp[i][j+s] += dp[i+1][j-nums[i]+s]
			}
		}
	}
	// dp[0][0] 平移
	return dp[0][s]
}

转化为 01 背包问题 §

将选择 + 和选择 - 的数分成两个集合：

1. positive + negative = sum
2. positive - negative = target

1 + 2 可推出：positive = (sum + target) / 2

也就是说，任何一个集合，只要累加和是 (sum + target) / 2，那么就一定对应一种 target 的方式

数组中每个数价值和重量都是这个数，当达到 (sum + target) / 2 时就是一种方法，每个数可以取或不取，至此已经转化为 01 背包问题了

虽然题目说 nums 是非负数组，但即使 nums 中有负数，因为能在每个数前面用 + 或者 - 号，所以即使 nums 中有负数，也可以把负数直接变成正数，也不会影响结果

剪枝：

1. nums 都是非负数，并且所有数的累加和是 sum，那么如果 target > sum || target < -sum，很明显没有任何方法可以达到 target，可以直接返回 0
2. nums 内部的数，不管怎么 + 和 -，最终的结果都一定不会改变奇偶性。所以，如果所有数的累加和是 sum，并且与 target 的奇偶性不一样，那么没有任何方法可以达到 target，可以直接返回 0

func findTargetSumWays(nums []int, target int) int {
	sum := 0
	for _, num := range nums {
		sum += num
	}
	if target > sum || target < -sum || (target&1)^(sum&1) == 1 {
		return 0
	}
	t := (sum + target) >> 1
	// dp[i][j]：前 i 个数，累加和等于 j 的选择方式有几种
	// dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i]]
	//           不选第 i 个数 + 选第 i 个数
	dp := make([]int, t+1)
	// 初始化：累加和等于 0 默认就有一种方式了，就是所有数都不选
	dp[0] = 1
	for _, num := range nums {
		for j := t; j >= num; j-- {
			dp[j] += dp[j-num]
		}
	}
	return dp[t]
}

题目4.最后一块石头的重量 II §

题目描述 §

有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

• 如果 x == y，那么两块石头都会被完全粉碎；
• 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。

提示：

• 1 <= stones.length <= 30
• 1 <= stones[i] <= 100

测试链接 §

1049.最后一块石头的重量 II

思路 §

和 题目3 转化为 01 背包问题思路差不多

将石头分成两堆，保证两堆重量尽量相等，即使不等也要是差值最小

即：遍历每个石头选或不选，选的总重量不能超过所有石头重量的一半

答案 §

func lastStoneWeightII(stones []int) int {
	sum := 0
	for _, stone := range stones {
		sum += stone
	}
	half := sum >> 1
 
	dp := make([]int, half+1)
	for _, stone := range stones {
		for j := half; j >= stone; j-- {
			dp[j] = max(
				dp[j],             // dp[i-1][j]，不选 stone
				dp[j-stone]+stone, // dp[i-1][j-stone]+stone，选 stone
			)
		}
	}
 
	// 差值 = 较重 - 较轻
	return (sum - dp[half]) - dp[half]
}

题目5.有依赖的背包模版 §

题目描述 §

物品分为两大类：主件和附件

• 主件的购买没有限制，钱够就可以
• 附件的购买有限制，该附件所归属的主件先购买，才能购买这个附件，并且钱够

例如，若想买打印机或扫描仪这样的附件，必须先购买电脑这个主件

每个主件最多有 2 个附件，并且附件不会再有附件，主件购买后，怎么去选择归属附件完全随意，钱够就可以

所有的物品编号都在 1~m 之间，每个物品有三个信息：价格 v、重要度 p、归属 q

价格就是花费，价格 * 重要度 就是收益，归属就是该商品是依附于哪个编号的主件（q == 0 代表是主件）

给定 m 件商品的信息，给定总钱数 n，返回在不违反购买规则的情况下最大的收益

测试链接 §

• 洛谷：P1064【NOIP2006 提高组】金明的预算方案
• 牛客：购物单

思路 §

和 经典 01 背包 一样的思路，差别是只考虑主件，附件在相应的主件买了之后分情况去讨论

答案 §

package main
 
import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)
 
const (
	MAXN = 33001
	MAXM = 61
)
 
var (
	n       int              // 总钱数
	m       int              // 物品数量
	cost    = [MAXM]int{}    // 花费
	val     = [MAXM]int{}    // 收益
	king    = [MAXM]bool{}   // 是否主件
	cnt     = [MAXM]int{}    // 有几个附件
	follows = [MAXM][2]int{} // 附件编号
	dp      = [MAXN]int{}
)
 
func main() {
	in := bufio.NewScanner(os.Stdin)
	in.Split(bufio.ScanWords)
	out := bufio.NewWriterSize(os.Stdout, 4096)
	for in.Scan() {
		// 总钱数
		n, _ = strconv.Atoi(in.Text())
		in.Scan()
		// 物品数量
		m, _ = strconv.Atoi(in.Text())
		v, p, q := 0, 0, 0
		clean()
		for i := 1; i <= m; i++ {
			// 价格
			in.Scan()
			v, _ = strconv.Atoi(in.Text())
			// 重要度
			in.Scan()
			p, _ = strconv.Atoi(in.Text())
			// 归属
			in.Scan()
			q, _ = strconv.Atoi(in.Text())
			cost[i] = v
			val[i] = v * p
			king[i] = q == 0
			if q != 0 {
				follows[q][cnt[q]] = i
				cnt[q]++
			}
		}
		fmt.Fprintln(out, compute())
	}
	out.Flush()
}
 
func clean() {
	for i := 1; i <= m; i++ {
		cnt[i] = 0
	}
}
 
func compute() int {
	// dp[i][j] : 前 i 个商品，只关心主商品，进行展开，花费不超过 j 的情况下，获得的最大收益
 
	// 初始化：dp[0][*] = 0 无商品的时候
	for j := 0; j <= n; j++ {
		dp[j] = 0
	}
	for i := 1; i <= m; i++ {
		// 只遍历主件
		if !king[i] {
			continue
		}
		for j := n; j >= cost[i]; j-- {
			dp[j] = max(
				dp[j],                // 不买当前主件
				dp[j-cost[i]]+val[i], // 只买当前主件
			)
			follow1 := -1
			if cnt[i] >= 1 {
				follow1 = follows[i][0]
			}
			follow2 := -1
			if cnt[i] >= 2 {
				follow2 = follows[i][1]
			}
			// 买当前主件 + 买附件 1
			if follow1 != -1 && j-cost[i]-cost[follow1] >= 0 {
				dp[j] = max(dp[j], dp[j-cost[i]-cost[follow1]]+val[i]+val[follow1])
			}
			// 买当前主件 + 买附件 2
			if follow2 != -1 && j-cost[i]-cost[follow2] >= 0 {
				dp[j] = max(dp[j], dp[j-cost[i]-cost[follow2]]+val[i]+val[follow2])
			}
			// 买当前主件 + 买附件 1 + 买附件 2
			if follow1 != -1 && follow2 != -1 && j-cost[i]-cost[follow1]-cost[follow2] >= 0 {
				dp[j] = max(dp[j], dp[j-cost[i]-cost[follow1]-cost[follow2]]+val[i]+val[follow1]+val[follow2])
			}
		}
	}
	return dp[n]
}

题目6.非负数组前 k 个最小的子序列和 §

题目描述 §

给定一个数组 nums，含有 n 个数字，都是非负数

给定一个正数 k，返回所有子序列中累加和最小的前 k 个累加和

子序列是包含空集的

数据规模：

• 1 <= n <= 10^5
• 1 <= nums[i] <= 10^6
• 1 <= k <= 10^5

测试链接 §

对数器验证

思路 §

01 背包的解法 §

dp[i][j]：前 i 个数中，子序列累加和等于 j 的子序列个数

状态转移：

1. 不要第 i 个数：前 i-1 个数组成的子序列累加和就要等于 j，即：dp[i-1][j]
2. 要第 i 个数：dp[i-1][j-nums[i]]

两种情况方案个数相加

答案：

dp[n][0] 往后取，dp[n] 代表考虑所有数

如：dp[n] = [1, 3, 2, ...], k = 5

则答案是：[0, 1, 1, 1, 2]

解释：dp[n][0] 取 1 个 0，dp[n][1] 取 3 个 1，dp[n][2] 取 1 个 2，够 k=5 个了，不用再往后取了

复杂度：

• 物品个数 $10^5$
• 背包容量大小是累加和 $10^5\ast 10^6=10^{11}$

那么时间复杂度是 $10^5\ast 10^{11}=10^{16}$ 规模的，远远超过 $10^7\backsim 10^8$（1 秒），必超时，根据数据量猜解法

借助堆 §

1. 先将数组从小到大排序
2. 再借助小根堆进行贪心
   • 要保证数组中没有负值，否则该贪心是错误的

复杂度：

• 时间复杂度：$O(n\ast lo{g}^n)+O(k\ast lo{g}^k)$
  • $O(n\ast lo{g}^n)$：数组排序
  • $O(k\ast lo{g}^k)$：k 轮，每轮从堆中出一个元素，进两个元素，堆的大小差不多是 k，调整代价为 $lo{g}^k$
• 空间复杂度：$O(k)$，堆的大小

答案 §

package main
 
import (
	"container/heap"
	"fmt"
	"math/rand"
	"sort"
)
 
// 暴力递归
func topKSum1(nums []int, k int) []int {
	allSubsequences := []int{}
	f(nums, &allSubsequences, 0, 0)
	sort.Ints(allSubsequences)
	return allSubsequences[:k]
}
 
// 暴力递归：得到所有子序列的和
func f(nums []int, ans *[]int, idx, sum int) {
	if idx == len(nums) {
		*ans = append(*ans, sum)
	} else {
		f(nums, ans, idx+1, sum)           // 不要 nums[idx]
		f(nums, ans, idx+1, sum+nums[idx]) // 要 nums[idx]
	}
}
 
// 01 背包解法
func topKSum2(nums []int, k int) []int {
	sum := 0
	for _, num := range nums {
		sum += num
	}
	dp := make([]int, sum+1)
	// 初始化：累加和等于 0 的方案默认就有一种：空集子序列
	dp[0] = 1
	for _, num := range nums {
		for j := sum; j >= num; j-- {
			dp[j] += dp[j-num]
		}
	}
	ans := make([]int, k)
	idx := 0
	for j := 0; j <= sum && idx < k; j++ {
		for i := 0; i < dp[j] && idx < k; i++ {
			ans[idx] = j
			idx++
		}
	}
	return ans
}
 
// 借助堆，最优解
func topKSum3(nums []int, k int) []int {
	sort.Ints(nums)
	n := len(nums)
	minHeap := make(MinHeap, 0, k+1)
	heap.Push(&minHeap, [2]int{0, nums[0]})
	ans := make([]int, k)
	// 空集
	ans[0] = 0
	for i := 1; i < k; i++ {
		cur := heap.Pop(&minHeap).([2]int)
		right := cur[0]
		sum := cur[1]
		ans[i] = sum
		if right+1 < n {
			// 不要 right，要 right+1
			heap.Push(&minHeap, [2]int{right + 1, sum - nums[right] + nums[right+1]})
			// 要 right，要 right+1
			heap.Push(&minHeap, [2]int{right + 1, sum + nums[right+1]})
		}
	}
	return ans
}
 
// [子序列的最右下标, 子序列的累加和]
type MinHeap [][2]int
 
func (h MinHeap) Len() int {
	return len(h)
}
 
func (h MinHeap) Less(a, b int) bool {
	// 按子序列的累加和组织小根堆
	return h[a][1] < h[b][1]
}
 
func (h MinHeap) Swap(a, b int) {
	h[a], h[b] = h[b], h[a]
}
 
func (h *MinHeap) Push(val interface{}) {
	*h = append(*h, val.([2]int))
}
 
func (h *MinHeap) Pop() interface{} {
	n := h.Len()
	res := (*h)[n-1]
	*h = (*h)[:n-1]
	return res
}
 
const (
	N          = 15
	V          = 40
	TEST_TIMES = 5000
)
 
func main() {
	for i := 0; i < TEST_TIMES; i++ {
		length := rand.Intn(N) + 1
		nums := randomArray(length)
		k := rand.Intn((1<<length)-1) + 1
		ans1 := topKSum1(nums, k)
		ans2 := topKSum2(nums, k)
		ans3 := topKSum3(nums, k)
		if !equals(ans1, ans2) || !equals(ans1, ans3) {
			panic("error")
		}
	}
	fmt.Println("ok")
}
 
func randomArray(length int) []int {
	arr := make([]int, length)
	for i := range arr {
		arr[i] = rand.Intn(V)
	}
	return arr
}
 
func equals(arr1, arr2 []int) bool {
	n := len(arr1)
	if n != len(arr2) {
		return false
	}
	for i := 0; i < n; i++ {
		if arr1[i] != arr2[i] {
			return false
		}
	}
	return true
}