自动搬运

查看原文

来自洛谷，原作者为

	while_true 走自己的路，让别人说去吧!

搬运于2025-08-24 22:42:00，当前版本为作者最后更新于2023-01-21 15:41:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

经典 01 背包题

• 首先介绍一下 01 背包，即一种 DP 问题，以放置物品为模型，每个物品只能放一次。其区分于完全背包（每个物品可以放无限多次），以及多重背包（每个物品有一个固定次数上限）。题中给出了 $N$ 个砝码及每个砝码的质量，要求我们求出可以称出质量的种数。由此想到转化为 01 背包。
• 本题作为 01 背包的模板题之一，其思想不难（前提是你掌握了 01 背包写法）。但是有几个坑点：

1. 上过初一的人都知道左物右码，这个题出的很不科学。 题中重点是天平两边都能放砝码，显然，由于天平两边放砝码的质量不一定相等，所以要在较轻一侧放一个一定质量的物体使其平衡。所以显然地，设物体质量为 $m_{thing}$，左盘砝码质量为 $m_l$，右盘砝码质量为 $m_r$，则有：

$$\left\{ \begin{array}{c} m_{thing}+m_l=m_r (m_l\le m_r)\\ m_{thing}+m_r=m_l (m_l\ge m_r) \end{array} \right. $$

即为:

$$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$ 炸了于是做了修改。