P8742 [蓝桥杯 2021 省 AB] 砝码称重 题解

while_true · 2023-01-21 15:41:32 · 题解

经典 01 背包题

• 首先介绍一下 01 背包，即一种 DP 问题，以放置物品为模型，每个物品只能放一次。其区分于完全背包（每个物品可以放无限多次），以及多重背包（每个物品有一个固定次数上限）。题中给出了 N 个砝码及每个砝码的质量，要求我们求出可以称出质量的种数。由此想到转化为 01 背包。
• 本题作为 01 背包的模板题之一，其思想不难（前提是你掌握了 01 背包写法）。但是有几个坑点：
  1. 上过初一的人都知道左物右码，这个题出的很不科学。 题中重点是天平两边都能放砝码，显然，由于天平两边放砝码的质量不一定相等，所以要在较轻一侧放一个一定质量的物体使其平衡。所以显然地，设物体质量为 m_{thing} ，左盘砝码质量为 m_l ，右盘砝码质量为 m_r ，则有：

即为:

2. 注意 dp 方程转移时要从大到小转移，否则存在越界。

代码构造

• 说了这么多，代码怎么写？有了以上结论，这变得容易了些：我们不妨设状态 f_{i,j} 表示枚举到第 i 个砝码时是否能够称出质量 j 。
  但是为什么这么设呢？ 有些人摸不着头脑。我们不妨这么想：线性 DP 本身是要以线性方式转移状态，本题中可以看作枚举每个砝码，因此状态定义中存在砝码（即 i ）。本题是要求 情况总数 ，所以我们想到一个类似于桶标记的方法定义状态（即定义 j 质量）。
• 那怎么写双重循环呢？外层循环很显然是枚举每个砝码，即将 i 从1枚举到 n ，但内层循环呢？其实也很简单，因为我们之前定义了 j 为枚举质量，所以我们可以将 j 从1开始枚举，枚举到所有砝码质量总和（因为质量最大就是砝码质量总和）。
• 因此，易推得 f_{i,j} 如何转移:
  1. 如果枚举到当前的砝码不放，那么对于枚举到的每一个质量，其情况都与枚举到上个砝码时的情况相同，且此方案显然是否可行取决于上一个方案是否可行。 即 f_{i,j} = f_{i-1,j} 。
  2. 如果之前一个砝码也没放，现在枚举到的砝码是第一个放的（即当前枚举到的 j 就是当前枚举到的砝码质量），那么这种方案显然可行，因此 f_{i,j}=1(j=W_i) 。
  3. 另外的情况，我们需要分类讨论：
     第一种情况： 将当前枚举到的砝码放置在右盘，右盘质量为 j ，那么显然还没有放置时右盘质量为 |j-W_i| 。为什么加绝对值，是因为上一个砝码有可能放在左盘或右盘（这里枚举 j 为右盘质量），所以只要上一个砝码能称出 |j-W_i| 的质量，当前砝码就可以称出 j 的质量。 即当 f_{i-1,|j-W_i|}=1 时， f_{i,j} = 1 。
     第二种情况： 将当前枚举的砝码放在左盘，那么类似地，当 f_{i-1,j+W_i}=1 时， f_{i,j}=1 。

因此，本题就很清楚了。至于具体代码……相信您可以凭自己实力写出来！

求过（小声）

• Update_2023.1.29 增加了描述；
• Update_2023.2.1 更改 \LaTeX 的排版。
• Update_2023.2.2 在数字和汉字间加空格（笑）。
• Update_2024.9.26 退役快一年后重回洛谷发现 \LaTeX 炸了于是做了修改。