前置知识: 讲解054 - 单调队列 讲解067、讲解068 - 二维动态规划及其空间压缩技巧 讲解073 - 01背包 讲解074 - 完全背包 【必备】课程的动态规划大专题从讲解066开始，建议从头开始学习会比较系统

多重背包：每一种物品给定数量的限制，进行可能性展开 多重背包的枚举优化：二进制分组优化（最常用）、单调队列优化（复杂度最好，理解稍难）

混合背包：多种背包模型的组合与转化

注意： 动态规划优化枚举是一个很大的话题，这节课讲了二进制分组优化、单调栈优化 动态规划优化枚举的技巧，在 讲解082 - 动态规划优化枚举的技巧 会有进一步的讲解 【扩展】课程阶段 也会有进一步的讲述

题目1 多重背包不进行枚举优化 宝物筛选 一共有n种货物, 背包容量为t 每种货物的价值(v[i])、重量(w[i])、数量(c[i])都给出 请返回选择货物不超过背包容量的情况下，能得到的最大的价值 测试链接 : https://www.luogu.com.cn/problem/P1776

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

宝物筛选 一共有n种货物, 背包容量为t 每种货物的价值(v[i])、重量(w[i])、数量(c[i])都给出 请返回选择货物不超过背包容量的情况下，能得到的最大的价值 测试链接 : https://www.luogu.com.cn/problem/P1776

for (int k = 1; k <= cnt; k <<= 1) {
    v[++m] = k * value;
    w[m] = k * weight;
    cnt -= k;
}
if (cnt > 0) {
    v[++m] = cnt * value;
    w[m] = cnt * weight;
}

核心在于： 可能有一些张数情况有重复计算，但是不会漏掉任何一种张数情况，也不会多算任何一种张数情况 因为是二进制分组，让原本0~cnt规模的枚举，变成了0~log(cnt)规模的枚举

题目3 观赏樱花 给定一个背包的容量t，一共有n种货物，并且给定每种货物的信息 花费(cost)、价值(val)、数量(cnt) 如果cnt == 0，代表这种货物可以无限选择 如果cnt > 0，那么cnt代表这种货物的数量 挑选货物的总容量在不超过t的情况下，返回能得到的最大价值 背包容量不超过1000，每一种货物的花费都>0 测试链接 : https://www.luogu.com.cn/problem/P1833

完全背包转化为多重背包，再把多重背包通过二进制分组转化为01背包

题目4 多重背包单调队列优化

宝物筛选 一共有n种货物, 背包容量为t 每种货物的价值(v[i])、重量(w[i])、数量(c[i])都给出 请返回选择货物不超过背包容量的情况下，能得到的最大的价值 测试链接 : https://www.luogu.com.cn/problem/P1776

注意： 需要理解 讲解054 - 单调队列，不然听不懂 理解难度稍微大一些，一定要配合具体例子来分析

题目5 混合背包 + 多重背包普通窗口优化 能成功找零的钱数种类 每一种货币都给定面值val[i]，和拥有的数量cnt[i] 想知道目前拥有的货币，在钱数为1、2、3…m时 能找零成功的钱数有多少 也就是说当钱数的范围是1~m 返回这个范围上有多少可以找零成功的钱数 比如只有3元的货币，数量是5张 m = 10 那么在1~10范围上，只有钱数是3、6、9时，可以成功找零 所以返回3表示有3种钱数可以找零成功 测试链接 : http://poj.org/problem?id=1742

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com