Skip to main content

背包型

David LiuNovember 22, 2024About 12 min

背包型

属于前缀型的一种

核心是有一个维度是val的和/积

你有一个背包，背包有最大承重

商店里有若干物品，每个物品有重量和价值

目标：不撑爆背包的前提下

  • 装下最多重量物品
  • 装下最大总价值的物品
  • 有多少种方式正好装满一书包物品

可以多维价值叠加 eg. 盈利计划

费用和价值互换：

  • 价值加起来比较小的话，可以与费用互换
    • 贿赂怪兽：

状态定义

恰好定义：

状态：f[i][j]表示考虑前i个物品，和为j的性质（最优值/方案数/可行性）

状态：f[i][j]=func(f[i-1][j], f[i-1][j-w[i-1]]+v[i-1])

边界：f[0][0]=1|方案数， true|可行性, 0|最大值, max|最小值

至多定义：

状态：f[i][j]表示考虑前i个物品，和为j的性质（最优值/方案数/可行性）

状态：f[i][j]=func(f[i-1][j], f[i-1][j-w[i-1]]+v[i-1])

边界：f[0][j]=1|方案数， true|可行性, 0|最优值

至少定义：

状态：f[i][j]表示考虑前i个物品，和为j的性质（最优值/方案数/可行性）

状态：f[i][j]=func(f[i-1][j], f[i-1][max{0,j-w[i-1]}]+v[i-1])

边界：f[0][0]=1|方案数， true|可行性, 0|最优值

Backpack 可行性背包

  • 要求不超过Target时能拼出的最大重量
  • 记录前个物品能不能拼出重量w

Backpack V, Backpack VI, 计数型背包

  • 要求有多少种方式拼出重量Target
  • Backpack V：记录前i个物品有多少种方式拼出重量w
  • Backpack VI：记录有多少种方式拼出重量w

Backpack Il, Backpack Ill,最值型背包

  • 题面：要求能拼出的最大价值
  • 记录f[i][w]=前i个种物品拼出重量w能得到的最大价值

关键点

  • 最后一步
    • 最后一个背包内的物品是娜个
    • 最后一个物品有没有进背包
  • 数组大学和最大承重target有关

空间优化

零一背包

01 背包

n个物品, m大小的背包，问最多能装多满

状态：f[i][j]表示考虑前i个物品，和为j的性质（最优值/方案数/可行性）

状态：f[i][j]=max(f[i-1][j],f[i-1][j-w[i-1]]+w[i-1])

分割等和子集

状态：f[i][j]表示考虑前i个物品，和为j的可行性

状态：f[i][j]=f[i-1][j] or f[i-1][j-w[i-1]]

答案：f % 2 == 0 && f[m / 2]

最小划分

将数组划分为两组，两组分别求和之后的差最小。狗家真题

= 数组中挑出若干数尽可能的填满一个大小为 SUM/2 的背包

石头碰撞

给出 N 个石头及其大小数组 每次选 2 个石头进行碰撞，大小分别为 x,y 碰撞之后会变成一个石头，大小变为 |x - y| 直到石头个数 < 2为止 问最后剩下来的石头最小是多少?

本质上这个题的答案=最小划分那一题的答案

外卖优惠券

你有一张满 X 元减 10 元的满减券和每个菜品的价格(整数)，每个菜最多只买一份。问最少买多少钱可以用得上这张外卖券?

方案一：挑选若干数之和 >= X 且和最小
= 挑选出一些“不加入购物车”的菜品 尽可能填满一个 SUM - X 的背包

方案二：参考下面的盈利计划

K 个逆序对数组 lc629.

状态：f[i][j]表示前i个数字，恰好构成j个逆序对的方案数

转移：f[i][j]=f[i][j-1]-f[i-1][j-i]+f[i-1][j]

边界：f[n][k]

贿赂怪兽

完全背包

Coin Change 零钱兑换

最小值

状态：f[i][j]表示考虑前i个物品，和为j的性质（最优值/方案数/可行性）

状态：f[i][j]=min(f[i-1][j], f[i][j-w[i-1]]+v[i-1])

边界：f[0][j]=max|最小值,f[0][0]=0

Coin Change II 零钱兑换II

方案数

状态：f[i][j]表示考虑前i个物品，和为j的性质（最优值/方案数/可行性）

状态：f[i][j]=min(f[i-1][j], f[i][j-w[i-1]]+v[i-1])

边界：f[0][j]=-1,f[0][0]=0

多重背包

状态： dp[i][j]，表示前 i 种物品放入容量为 j 的背包中能够获得的最大价值。

转移：dp[i][j]=max(dp[i-1][j-k*w[i-1]]) k in [0,n[i-1]]

实现思路：

  1. 枚举容量后枚举，后面计算时记得带着k
  2. 枚举物品后枚举，本质是将i物品拆成n[i-1]个物品各自计算01背包

多维费用

盈利计划

多维费用背包

有n个项目，G个人，每个项目需要用group[i]个人，可以获得profit[i]的利润，一个人不能同时参与多个项目，求利润最少为P的方案总数

求方案数、有和信息；和=>背包DP

有哪些信息应该放到状态中？项目数、人数、利润

状态：f[i][j][k]表示前i个项目，用了j个人，获得至少k的收益的方案总数

转移：f[i][j][k]=f[i-1][j][k]+f[i-1][j-g[i-1][k-p[i-1]]]

边界：f[0][0][0]=1

答案：sum{f[n][i][p]}

注：group[i-1]是第i个项目需要用的人数（第i个数index=i-1)

j>=group[i-1]时才可以选择做第i个项目

如果k-profit[i-1]<0，则让这个维度的数值=0

可以滚i

另一种状态表示方法

状态：f[i][j][k]表示前 i 个项目，用至多 j 个人，获得至少 k 收益的方案总数

转移：f[i][j][k]=f[i-1][j][k]+f[i-1][j-g[i-1]][k-p[i-1]]

边界：f[0][i][0]=1

答案：f[n][G][P]

Ones And Zeroes / 0s and 1s

状态：f[i][j][k]为前i个串，最多能有多少个，被j个0和k个1组成

转移：f[i][j][k]=max{f[i-1][j][k], f[i-1][j-ai][j-bi]}

K Sum

给定数组A，包含n个互不相等的正整数

问有多少种方式从中找出K个数，使得它们的和是Target

二维费用

状态：f[i][j][k]表示前i物品，j费用，k选中

转移：f[i][j][k]=f[i-1][j][k]+f[i-1][j-a[i-1]][k-1]|j>=a[i-1]

老鼠游戏

浮点数组合和

合并石头的最低成本

分组背包

按组来枚举，变成以组为单位的0/1背包，费用有多种，枚举组内物品选一个

考试策略（美团）

有一场考试时间为 120 分钟的考试，有多道题目且作答顺序不受限制。对于第 i 道题目，你有三种不同的策略可以选择:

  1. 直接跳过这道题目，不花费时间，本题得 0 分。
  2. 只做这道题目一部分，花费 p_time[i] 分钟的时间，本题可以得到 p_score[i] 分。
  3. 做完整道题目，花费 f_time[i] 分钟的时间，本题可以得到 f_score[i] 分。

分组01背包，每组是一个题，组内三个方案不做、部分、全部

状态：dp[i][j]表示选做前 i 道题，在考试 j 分钟时能得到的最高分数

浮点数组合和

给 n 个 >= 0 的 float, 每个数可以向上或者向下取整，调整目标是所有数之和为target，代价是每个数调整后差值绝对值，问最小调整代价所对应的具体方案

分组01背包，每组是一个数，组内两个方案向上或向下

状态：f[i][j]表示前i个数，凑出j的和，最小的调整代价是多少

转移：

边界：

背包总结

教程

分类

  • 部分背包，分数背包，贪心

  • 零一背包

  • 完全背包

  • 多重背包

  • 混合背包

  • 多维背包

  • 分组背包

  • 依赖背包，树形DP

这题目和完全背包问题很类似。基本的方程只需将完全背包问题的方程略微一改即可，因为对于第i种物品有n[i]+1种策略：取0件，取1件……取n[i]件。令f[i][v]表示前i种物品恰放入一个容量为v的背包的最大权值，则有状态转移方程：

f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]}

复杂度是O(V*Σn[i])。

混合背包

01+完全

考虑到在P01和P02中给出的伪代码只有一处不同，故如果只有两类物品：一类物品只能取一次，另一类物品可以取无限次，那么只需在对每个物品应用转移方程时，根据物品的类别选用顺序或逆序的循环即可，复杂度是O(VN)。伪代码如下：

for i=1..N
    if 第i件物品属于01背包
        for v=V..0
            f[v]=max{f[v],f[v-c[i]]+w[i]};
    else if 第i件物品属于完全背包
        for v=0..V
            f[v]=max{f[v],f[v-c[i]]+w[i]};

01+完全+多重

如果再加上有的物品最多可以取有限次，那么原则上也可以给出O(VN)的解法：遇到多重背包类型的物品用单调队列解即可。但如果不考虑超过NOIP范围的算法的话，用P03中将每个这类物品分成O(log n[i])个01背包的物品的方法也已经很优了。

当然，更清晰的写法是调用我们前面给出的三个相关过程。

for i=1..N
    if 第i件物品属于01背包
        ZeroOnePack(c[i],w[i])
    else if 第i件物品属于完全背包
        CompletePack(c[i],w[i])
    else if 第i件物品属于多重背包
        MultiplePack(c[i],w[i],n[i])

在最初写出这三个过程的时候，可能完全没有想到它们会在这里混合应用。我想这体现了编程中抽象的威力。如果你一直就是以这种“抽象出过程”的方式写每一类背包问题的，也非常清楚它们的实现中细微的不同，那么在遇到混合三种背包问题的题目时，一定能很快想到上面简洁的解法，对吗？

分组背包

有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

这个问题变成了每组物品有若干种策略：是选择本组的某一件，还是一件都不选。也就是说设f[k][v]表示前k组物品花费费用v能取得的最大权值，则有：

f[k][v]=max{f[k-1][v],f[k-1][v-c[i]]+w[i]|物品i属于组k}

使用一维数组的伪代码如下：

for 所有的组k
    for v=V..0
        for 所有的i属于组k
            f[v]=max{f[v],f[v-c[i]]+w[i]}

注意这里的三层循环的顺序，甚至在本文的第一个beta版中我自己都写错了。“for v=V..0”这一层循环必须在“for 所有的i属于组k”之外。这样才能保证每一组内的物品最多只有一个会被添加到背包中。

另外，显然可以对每组内的物品应用P02中“一个简单有效的优化”。

分组的背包问题将彼此互斥的若干物品称为一个组，这建立了一个很好的模型。不少背包问题的变形都可以转化为分组的背包问题（例如P07），由分组的背包问题进一步可定义“泛化物品”的概念，十分有利于解题。

依赖背包

这种背包问题的物品间存在某种“依赖”的关系。也就是说，i依赖于j，表示若选物品i，则必须选物品j。为了简化起见，我们先设没有某个物品既依赖于别的物品，又被别的物品所依赖；另外，没有某件物品同时依赖多件物品。

更一般的问题是：依赖关系以图论中“森林”的形式给出（森林即多叉树的集合），也就是说，主件的附件仍然可以具有自己的附件集合，限制只是每个物品最多只依赖于一个物品（只有一个主件）且不出现循环依赖。

解决这个问题仍然可以用将每个主件及其附件集合转化为物品组的方式。唯一不同的是，由于附件可能还有附件，就不能将每个附件都看作一个一般的01背 包中的物品了。若这个附件也有附件集合，则它必定要被先转化为物品组，然后用分组的背包问题解出主件及其附件集合所对应的附件组中各个费用的附件所对应的价值。

事实上，这是一种树形DP，其特点是每个父节点都需要对它的各个儿子的属性进行一次DP以求得自己的相关属性。这已经触及到了“泛化物品”的思想。看完P08后，你会发现这个“依赖关系树”每一个子树都等价于一件泛化物品，求某节点为根的子树对应的泛化物品相当于求其所有儿子的对应的泛化物品之和。

NOIP2006的那道背包问题我做得很失败，写了上百行的代码，却一分未得。后来我通过思考发现通过引入“物品组” 和“依赖”的概念可以加深对这题的理解，还可以解决它的推广问题。用物品组的思想考虑那题中极其特殊的依赖关系：物品不能既作主件又作附件，每个主件最多 有两个附件，可以发现一个主件和它的两个附件等价于一个由四个物品组成的物品组，这便揭示了问题的某种本质。

David's Blog
Copyright © 2025 David Liu