前置知识：单调队列、讲解067、讲解068 二维动态规划及其空间压缩技巧、01 背包、完全背包

多重背包、混合背包

多重背包：每一种物品给定数量的限制，进行可能性展开
- 不进行枚举优化：题目1
- 多重背包的枚举优化之二进制分组优化（最常用）：题目2、题目3
- 多重背包的枚举优化之单调队列优化（复杂度最好，理解稍难）：题目4
混合背包：多种背包模型的组合与转化
- 题目5

备注

动态规划优化枚举是一个很大的话题，这节课讲了二进制分组优化、单调栈优化

动态规划优化枚举的技巧，在动态规划优化枚举的技巧会有进一步的讲解

【扩展】课程阶段也会有进一步的讲述

题目1.多重背包不进行枚举优化模版

题目描述

一共有 n 种货物, 背包容量为 w

每种货物的价值(v[i])、重量(w[i])、数量(m[i])都给出

请返回选择货物不超过背包容量的情况下，能得到的最大的价值

数据规模：

$1 \leq n \leq 100$
$0 \leq w \leq 4 * 1 0^{4}$
$n \leq \sum m_{i} \leq 1 0^{5}$

测试链接

P1776 宝物筛选

思路

同 01 背包，只是在每一种物品给定的数量进行可能性展开：选 0 件、1 件、…

答案

package main
 
import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)
 
const (
	MAXN = 101
	MAXW = 40001
)
 
var (
	n    int
	w    int
	val  = [MAXN]int{}
	cost = [MAXN]int{}
	cnt  = [MAXN]int{}
	dp   = [MAXW]int{}
)
 
func main() {
	// s := `4 20
	// 3 9 3
	// 5 9 1
	// 9 4 2
	// 8 1 3`
	// in := bufio.NewScanner(strings.NewReader(s))
	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()
		w, _ = strconv.Atoi(in.Text())
		for i := 1; i <= n; i++ {
			in.Scan()
			val[i], _ = strconv.Atoi(in.Text())
			in.Scan()
			cost[i], _ = strconv.Atoi(in.Text())
			in.Scan()
			cnt[i], _ = strconv.Atoi(in.Text())
		}
		fmt.Fprintln(out, compute2())
	}
	out.Flush()
}
 
// 严格位置依赖的动态规划
func compute1() int {
	dp := make([][]int, n+1)
	for i := range dp {
		dp[i] = make([]int, w+1)
	}
	// 初始化：dp[0][*] = 0，表示没有货物的情况下，背包容量不管是多少，最大价值都是 0
 
	for i := 1; i <= n; i++ {
		for j := 0; j <= w; j++ {
			// 一件 i 不选
			dp[i][j] = dp[i-1][j]
			// k <= cnt[i]：选的数量不超过 i 物品的拥有数量
			// j-cost[i]*k >= 0：防止 dp 表下标越界
			for k := 1; k <= cnt[i] && j-cost[i]*k >= 0; k++ {
				dp[i][j] = max(dp[i][j], dp[i-1][j-cost[i]*k]+val[i]*k)
			}
		}
	}
	return dp[n][w]
}
 
// 空间压缩
func compute2() int {
	for j := 0; j <= w; j++ {
		dp[j] = 0
	}
	for i := 1; i <= n; i++ {
		for j := w; j >= 0; j-- {
			for k := 1; k <= cnt[i] && j-cost[i]*k >= 0; k++ {
				dp[j] = max(dp[j], dp[j-cost[i]*k]+val[i]*k)
			}
		}
	}
	return dp[w]
}

复杂度

时间复杂度： $O (n * w * \sum m_{i})$
空间复杂度：
- 严格位置依赖的动态规划： $O (n * w)$
- 空间压缩： $O (w)$

题目2.多重背包通过二进制分组转化成 01 背包模版

题目描述

和题目 1 是同一道题

思路

通过二进制分组进行枚举优化，将多重背包转化成 01 背包

二进制分组：将有数量限制的一个物品，看成数量限制为 1 的多个物品（即：01 背包）

如：某个物品的信息为价值 v、重量 w、数量 m[i]=12

将其分成：

$2^{0} = 1$ ：价值 v、重量 w
$2^{1} = 2$ ：价值 2v、重量 2w
$2^{2} = 4$ ：价值 4v、重量 4w
$12 - 1 - 2 - 4 = 5 （ < 2^{3} = 8 ）$ ：价值 5v、重量 5w

这样的 01 背包问题

原问题的选 1 件原物品，相当于只选 01 背包的 1 号物品
原问题的选 2 件原物品，相当于只选 01 背包的 2 号物品
原问题的选 3 件原物品，相当于只选 01 背包的 1、2 号物品（1+2=3）
原问题的选 4 件原物品，相当于只选 01 背包的 3 号物品
原问题的选 5 件原物品，相当于只选 01 背包的 1、3 号物品，或只选 4 号物品
…
原问题的选 12 件原物品，相当于选 01 背包的 1、2、3、4 号物品（1+2+4+5=12）

也就是：通过选择新物品的 01 背包，可以完全覆盖多重背包的所有选择情况，可能相同的数量有多种选择情况（如：原问题的选 5 件原物品，相当于只选 01 背包的 1、3 号物品，或只选 4 号物品）、但绝不可能多选（最多就是全选，正好等于 12）、少选（都不选就是 0）、漏选（不会有组合不出 0~12 之间数的情况）

多重背包问题一般都使用二进制分组这种技巧，虽然时间复杂度不如单调队列优化的版本，但是好写，而且即便是比赛，时间复杂度也达标，二进制分组的时间复杂度为 $O (l o g^{co u n t})$

答案

package main
 
import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)
 
const (
	MAXN = 1001 // 二进制分组，物品数量会变多
	MAXW = 40001
)
 
var (
	n    int
	w    int
	m    int // 二进制分组后的物品数量
	val  = [MAXN]int{}
	cost = [MAXN]int{}
	dp   = [MAXW]int{}
)
 
func main() {
	// s := `4 20
	// 3 9 3
	// 5 9 1
	// 9 4 2
	// 8 1 3`
	// in := bufio.NewScanner(strings.NewReader(s))
	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()
		w, _ = strconv.Atoi(in.Text())
		m = 0
		value, weight, count := 0, 0, 0
		for i := 1; i <= n; i++ {
			in.Scan()
			value, _ = strconv.Atoi(in.Text())
			in.Scan()
			weight, _ = strconv.Atoi(in.Text())
			in.Scan()
			count, _ = strconv.Atoi(in.Text())
 
			// 核心逻辑：二进制分组
			for k := 1; k <= count; k <<= 1 {
				m++
				val[m] = k * value
				cost[m] = k * weight
				count -= k
			}
			if count > 0 {
				m++
				val[m] = count * value
				cost[m] = count * weight
			}
		}
		fmt.Fprintln(out, compute())
	}
	out.Flush()
}
 
// 01 背包的空间压缩代码模版
func compute() int {
	for j := 0; j <= w; j++ {
		dp[j] = 0
	}
	for i := 1; i <= m; i++ {
		for j := w; j >= cost[i]; j-- {
			dp[j] = max(dp[j], dp[j-cost[i]]+val[i])
		}
	}
	return dp[w]
}

复杂度

时间复杂度： $O ((l o g_{2}^{m 1} + l o g_{2}^{m 2} + \dots) * w)$ ，对每一种商品的个数取 $l o g$ ，时间复杂度虽然大于 $O (n * w)$ ，但也不会大多少
空间复杂度：
- 严格位置依赖的动态规划： $O (m * w)$
- 空间压缩： $O (w)$

题目3.观赏樱花

题目描述

给定一个背包的容量 w，一共有 n 种货物，并且给定每种货物的信息：花费(cost)、价值(val)、数量(cnt)

如果 cnt == 0，代表这种货物可以无限选择
如果 cnt > 0，那么 cnt 代表这种货物的数量

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

数据保证：背包容量不超过 1000，每一种货物的花费都 >0

测试链接

P1833 樱花

思路

因为背包容量不超过 1000，每一种货物的花费都 >0，所以一个物品最多也就能装 1000 个

即：可以将 cnt == 0 的无限选择货物，看成 cnt == 1000，就转化成了多重背包问题

答案

package main
 
import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)
 
const (
	MAXN   = 100001 // 二进制分组，物品数量会变多
	MAXW   = 1001
	ENOUGH = 1001
)
 
var (
	n           int
	w           int
	m           int // 二进制分组后的物品数量
	val         = [MAXN]int{}
	cost        = [MAXN]int{}
	dp          = [MAXW]int{}
	startHour   int
	startMinute int
	endHour     int
	endMinute   int
)
 
func main() {
	// s := `6:50 7:00 3
	// 2 1 0
	// 3 3 1
	// 4 5 4`
	// in := bufio.NewScanner(strings.NewReader(s))
	in := bufio.NewScanner(os.Stdin)
	in.Split(bufio.ScanWords)
	out := bufio.NewWriterSize(os.Stdout, 4096)
	for in.Scan() {
		tmp := strings.Split(in.Text(), ":")
		startHour, _ = strconv.Atoi(tmp[0])
		startMinute, _ = strconv.Atoi(tmp[1])
		in.Scan()
		tmp = strings.Split(in.Text(), ":")
		endHour, _ = strconv.Atoi(tmp[0])
		endMinute, _ = strconv.Atoi(tmp[1])
		if startMinute > endMinute {
			endHour--
			endMinute += 60
		}
		// 计算背包容量
		w = (endHour-startHour)*60 + (endMinute - startMinute)
		in.Scan()
		n, _ = strconv.Atoi(in.Text())
		m = 0
		value, weight, count := 0, 0, 0
		for i := 1; i <= n; i++ {
			in.Scan()
			weight, _ = strconv.Atoi(in.Text())
			in.Scan()
			value, _ = strconv.Atoi(in.Text())
			in.Scan()
			count, _ = strconv.Atoi(in.Text())
			if count == 0 {
				count = ENOUGH
			}
			// 二进制分组
			for k := 1; k <= count; k <<= 1 {
				m++
				val[m] = k * value
				cost[m] = k * weight
				count -= k
			}
			if count > 0 {
				m++
				val[m] = count * value
				cost[m] = count * weight
			}
		}
		fmt.Fprintln(out, compute())
	}
	out.Flush()
}
 
// 01 背包的空间压缩代码模版
func compute() int {
	for j := 0; j <= w; j++ {
		dp[j] = 0
	}
	for i := 1; i <= m; i++ {
		for j := w; j >= cost[i]; j-- {
			dp[j] = max(dp[j], dp[j-cost[i]]+val[i])
		}
	}
	return dp[w]
}

题目4.多重背包通过单调队列优化枚举

题目描述

和题目 1 是同一道题

思路

通过单调队列优化的前提：j 根据余数分组

单调队列优化：维持窗口最大值，不用每一个 dp[j] 都算 max

答案

package main
 
import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)
 
const (
	MAXN = 101
	MAXW = 40001
)
 
var (
	n          int
	w          int
	val        = [MAXN]int{}
	cost       = [MAXN]int{}
	cnt        = [MAXN]int{}
	dp         = [MAXW]int{}
	queue      = [MAXW]int{}
	head, tail = 0, 0
)
 
func main() {
	// s := `4 20
	// 3 9 3
	// 5 9 1
	// 9 4 2
	// 8 1 3`
	// in := bufio.NewScanner(strings.NewReader(s))
	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()
		w, _ = strconv.Atoi(in.Text())
		for i := 1; i <= n; i++ {
			in.Scan()
			val[i], _ = strconv.Atoi(in.Text())
			in.Scan()
			cost[i], _ = strconv.Atoi(in.Text())
			in.Scan()
			cnt[i], _ = strconv.Atoi(in.Text())
		}
		fmt.Fprintln(out, compute2())
	}
	out.Flush()
}
 
// 严格位置依赖的动态规划 + 单调队列优化枚举
func compute1() int {
	dp := make([][]int, n+1)
	for i := range dp {
		dp[i] = make([]int, w+1)
	}
	// 初始化：dp[0][*] = 0，表示没有货物的情况下，背包容量不管是多少，最大价值都是 0
 
	for i := 1; i <= n; i++ {
		// 相同余数为一组，余数取 0 ~ cost[i] - 1，并且余数不可能超出背包容量
		for mod := 0; mod <= min(w, cost[i]-1); mod++ {
			head, tail = 0, 0
			// 遍历同一组（相同余数）的 j
			for j := mod; j <= w; j += cost[i] {
				// X：queue[tail-1]，队尾元素
				// Y：j，当前将要入队元素
				for head < tail && dp[i-1][queue[tail-1]]+inc(j-queue[tail-1], i) <= dp[i-1][j] {
					// queue[tail-1] 是队列尾部的列号 VS. j 这个列号
					// 指标之间 PK
					tail--
				}
				queue[tail] = j
				tail++
				// 检查单调队列队头的列号，是否过期
				if j-queue[head] == cost[i]*(cnt[i]+1) {
					head++
				}
				// dp[i][j] = dp[i-1][拥有最强指标的列] + (j - 拥有最强指标的列) / i号物品重量 * i号物品价值
				dp[i][j] = dp[i-1][queue[head]] + inc(j-queue[head], i)
			}
		}
	}
	return dp[n][w]
}
 
// 空间压缩 + 单调队列优化枚举
func compute2() int {
	for j := 0; j <= w; j++ {
		dp[j] = 0
	}
	for i := 1; i <= n; i++ {
		for mod := 0; mod <= min(w, cost[i]-1); mod++ {
			head, tail = 0, 0
			// 因为空间压缩时，关于 j 的遍历是从右往左，而不是从左往右
			// 所以先让 dp[i-1][...右侧的几个位置] 进入窗口
			for j, k := w-mod, 0; j >= 0 && k <= cnt[i]; j, k = j-cost[i], k+1 {
				for head < tail && dp[j]+inc(queue[tail-1]-j, i) >= dp[queue[tail-1]] {
					tail--
				}
				queue[tail] = j
				tail++
			}
			// 然后 j 开始从右往左遍历
			// 注意，因为 j 从右往左遍历，所以：
			// 更靠右的 j 位置更早进入窗口
			// 更靠左的 j 位置更晚进入窗口
			for j := w - mod; j >= 0; j -= cost[i] {
				dp[j] = dp[queue[head]] + inc(j-queue[head], i)
				// 求解完 dp[j]
				// 接下来要去求解 dp[j-cost[i]] 了（根据余数分组）
				// 所以看看窗口最左的下标是不是 j（其实代表 dp[i-1][j] 的值）
				// 是的话，说明最左下标过期了，要弹出
				if queue[head] == j {
					head++
				}
				// 最后
				// 因为接下来要去求解 dp[j-cost[i]]
				// 所以新的 dp[i-1][enter] 要进入窗口了
				// 用单调队列的更新方式让其进入
				enter := j - cost[i]*(cnt[i]+1)
				if enter >= 0 {
					for head < tail && dp[enter]+inc(queue[tail-1]-enter, i) >= dp[queue[tail-1]] {
						tail--
					}
					queue[tail] = enter
					tail++
				}
			}
		}
	}
	return dp[w]
}
 
// s 的容量用来装 i 号商品，可以得到多少价值
func inc(s, i int) int {
	return s / cost[i] * val[i]
}

复杂度

时间复杂度： $O (n * w)$
- 按余数分组后遍历每一组的每个数，就是 $w$
- 枚举同组的每个数：每个数只进出单调队列一次，平均时间复杂度为 $O (1)$
空间复杂度： $O (w + w / ma x (cos t))$
- $w$ ：空间压缩后的 dp 表大小
- $w / ma x (cos t)$ ：单调队列大小，即： $同组元素的数量 = 背包容量 / 组数量$

题目5.混合背包 + 多重背包普通窗口优化

题目描述

每一种货币都给定面值 val[i]，和拥有的数量 cnt[i]

想知道目前拥有的货币，在钱数为 $1 、 2 、 3 、 ... 、 m$ 时，能找零成功的钱数有多少个

也就是说当钱数的范围是 1~m，返回这个范围上有多少可以找零成功的钱数

比如只有 3 元的货币，数量是 5 张，m = 10

那么在 1~10 范围上，只有钱数是 3、6、9 时，可以成功找零

所以返回 3，表示有 3 种钱数可以找零成功

测试链接

能成功找零的钱数种类

思路

一种钱个数为 1 时：01 背包
一种钱的个数乘价值大于总背包容量时，相当于无限用：完全背包
否则说明这种钱的个数有限制：多重背包
- 使用单调队列优化（滑动窗口）
- 因为要求的不是最大价值，而是是否可以成功找零，只需要维持窗口中 true 的个数信息即可，使用一个变量维持，都省去了单调队列（滑动窗口）的空间

答案

该测试网站无 Go 环境，使用 Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;
 
public class Main {
	public static int MAXN = 101;
	public static int MAXM = 100001;
 
	public static int[] val = new int[MAXN];
	public static int[] cnt = new int[MAXN];
	public static boolean[] dp = new boolean[MAXM];
	public static int n, m;
 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StreamTokenizer in = new StreamTokenizer(br);
		PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		while (in.nextToken() != StreamTokenizer.TT_EOF) {
			n = (int) in.nval;
			in.nextToken();
			m = (int) in.nval;
			if (n != 0 || m != 0) {
				for (int i = 1; i <= n; i++) {
					in.nextToken();
					val[i] = (int) in.nval;
				}
				for (int i = 1; i <= n; i++) {
					in.nextToken();
					cnt[i] = (int) in.nval;
				}
				out.println(compute());
			}
		}
		out.flush();
		out.close();
		br.close();
	}
 
	// 严格位置依赖的动态规划：略
 
	// 空间压缩
	public static int compute() {
		Arrays.fill(dp, 1, m + 1, false);
		dp[0] = true;
		for (int i = 1; i <= n; i++) {
			if (cnt[i] == 1) {
				// 01 背包
				// 空间压缩实现是从右往左更新的
				for (int j = m; j >= val[i]; j--) {
					if (dp[j - val[i]]) {
						dp[j] = true;
					}
				}
			} else if (val[i] * cnt[i] > m) {
				// 完全背包
				// 空间压缩实现是从左往右更新的
				for (int j = val[i]; j <= m; j++) {
					if (dp[j - val[i]]) {
						dp[j] = true;
					}
				}
			} else {
				// 多重背包的空间压缩实现
				// 根据余数分组
				// 每一组都是从右往左更新的
				for (int mod = 0; mod < val[i]; mod++) {
					int trueCnt = 0;
					for (int j = m - mod, size = 0; j >= 0 && size <= cnt[i]; j -= val[i], size++) {
						trueCnt += dp[j] ? 1 : 0;
					}
					for (int j = m - mod, l = j - val[i] * (cnt[i] + 1); j >= 1; j -= val[i], l -= val[i]) {
						if (dp[j]) {
							trueCnt--;
						} else {
							if (trueCnt != 0) {
								dp[j] = true;
							}
						}
						if (l >= 0) {
							trueCnt += dp[l] ? 1 : 0;
						}
					}
				}
			}
		}
		int ans = 0;
		for (int i = 1; i <= m; i++) {
			if (dp[i]) {
				ans++;
			}
		}
		return ans;
	}
}

复杂度

时间复杂度： $O (n * m)$
空间复杂度： $O (m)$

My-Notes

Explorer

057.多重背包、混合背包

多重背包、混合背包

备注

题目1.多重背包不进行枚举优化模版

题目描述

测试链接

思路

答案

复杂度

题目2.多重背包通过二进制分组转化成 01 背包模版

题目描述

思路

答案

复杂度

题目3.观赏樱花

题目描述

测试链接

思路

答案

题目4.多重背包通过单调队列优化枚举

题目描述

思路

答案

复杂度

题目5.混合背包 + 多重背包普通窗口优化

题目描述

测试链接

思路

答案

复杂度

Graph View

Table of Contents

Backlinks

My-Notes

Explorer

057.多重背包、混合背包

多重背包、混合背包 §

备注 §

题目1.多重背包不进行枚举优化模版 §

题目描述 §

测试链接 §

思路 §

答案 §

复杂度 §

题目2.多重背包通过二进制分组转化成 01 背包模版 §

题目描述 §

思路 §

答案 §

复杂度 §

题目3.观赏樱花 §

题目描述 §

测试链接 §

思路 §

答案 §

题目4.多重背包通过单调队列优化枚举 §

题目描述 §

思路 §

答案 §

复杂度 §

题目5.混合背包 + 多重背包普通窗口优化 §

题目描述 §

测试链接 §

思路 §

答案 §

复杂度 §

Graph View

Table of Contents

Backlinks

多重背包、混合背包

备注

题目1.多重背包不进行枚举优化模版

题目描述

测试链接

思路

答案

复杂度

题目2.多重背包通过二进制分组转化成 01 背包模版

题目描述

思路

答案

复杂度

题目3.观赏樱花

题目描述

测试链接

思路

答案

题目4.多重背包通过单调队列优化枚举

题目描述

思路

答案

复杂度

题目5.混合背包 + 多重背包普通窗口优化

题目描述

测试链接

思路

答案

复杂度