GESP 题解库 / 7 级题解 / [GESP202506 七级] 调味平衡 · 第 7 / 24 题
GESP202506 七级 · P13018 · 中等

调味平衡

每种食材选或不选,在酸度和 = 甜度和的前提下,让两者之和最大。

📊
n ≤ 100,aᵢ, bᵢ ≤ 500
数据规模
🧮
100001
差值数组长度
⚡
O(n × 10⁵) ≈ 10⁷
时间复杂度
🎯
差值背包
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

小 A 有 n 种食材,第 i 种食材的酸度为 aᵢ、甜度为 bᵢ。每种食材可以选入料理,也可以不选。

料理的酸度 A 是所选食材酸度之和,甜度 B 是所选食材甜度之和。若 A = B,则称调味平衡。在保证平衡的前提下,求 A + B 的最大值。

💡
人话翻译:从 n 件物品中挑出一个子集,使 Σa = Σb,并让 Σa + Σb 尽量大。
因为平衡时 Σa = Σb,所以目标等价于让 Σa 尽量大(答案就是 2 × Σa)。
核心难点:"两个维度"(酸度、甜度)怎么同时兼顾?把 (A, B) 压缩成一个"差值" d = A − B,平衡就是 d = 0,这样就变成了一个一维背包。

🔍 关键词提取

差值背包0/1 背包子集和偏移处理滚动数组

已知条件

项目说明
输入第一行 n;随后 n 行每行两个正整数 aᵢ, bᵢ
输出平衡前提下 A + B 的最大值(可以为 0)
数据范围1 ≤ n ≤ 100,1 ≤ aᵢ, bᵢ ≤ 500
部分分40%:n ≤ 10 且 aᵢ, bᵢ ≤ 10;另有 20%:n ≤ 50 且 ≤ 10
空集也算方案什么都不选时 A = B = 0,合法,答案为 0
差值上界每件差值 |aᵢ − bᵢ| ≤ 499,n = 100 → 总差值 |d| ≤ 50000

需要解决的问题

02
思维导图
整理解题思路的全貌
⚖️ Σa = Σb 时最大化 Σa + Σb
🧠 模型转化
每种食材二选一 → 0/1 背包
平衡条件 Σa = Σb → 差值为 0
目标 A + B = 2Σa → 只需最大化 Σa
把两维 (A, B) 压成一维差值 d
📦 状态定义
dp[d] = 差值为 d 时最大的 Σa
d = Σa − Σb
dp[偏移] = 0 表示空集
其余状态初始为 −1(不可达)
🔄 转移方程
不选第 i 件:dp′ 继承 dp
选第 i 件:差值增加 aᵢ − bᵢ
dp′[d + aᵢ − bᵢ] = max(…, dp[d] + aᵢ)
用 ndp 双数组防止重复选
⚠️ 易错点
不可达用 0 初始化(0 是合法值)
原地更新导致同一件被选多次
忘记加偏移量 50000
以为必须选至少一件(空集和为 0)
03
样例手算推导
样例的完整推演

🧮 样例 1:三件食材 (1,2) (2,4) (3,2),答案 8

n = 3,一共只有 2³ = 8 种选法,先把它们全部列出来。

选法酸度 A甜度 BA = B ?A + B
空集 {}00✓ 平衡0
{1} (1,2)12✗—
{2} (2,4)24✗—
{3} (3,2)32✗—
{1,2}36✗—
{1,3}44✓ 平衡8
{2,3}56✗—
{1,2,3}68✗—

只有 {1,3} 平衡,A + B = 4 + 4 = 8 ✓

1
用差值背包核对(逐步更新 dp)

初始:dp[0] = 0(空集)

读入 (1,2),差值 −1:dp[−1] = 1,dp[0] 仍为 0

读入 (2,4),差值 −2:由 dp[0] → dp[−2] = 2;由 dp[−1] → dp[−3] = 3

读入 (3,2),差值 +1:由 dp[−1] = 1 → dp[0] = max(0, 1 + 3) = 4

最终 dp[0] = 4 → 答案 2 × 4 = 8

✅ 与枚举一致

⚠️
注意这一步:"由 dp[−1] = 1 得到 dp[0] = 4",含义是把 1 号食材和 3 号食材一起选上:酸度 1 + 3 = 4,甜度 2 + 2 = 4,差值刚好回到 0。
差值背包记录的只是"最大 Σa",并不关心具体选了哪些——这正是它能压缩状态的原因。

🧮 样例 2:五件食材,答案 2

食材为 (1,1)、(2,3)、(6,1)、(8,2)、(5,7)。这次有 2⁵ = 32 种选法,我们用"差值"的眼光看:

选法酸度 A甜度 B差值 A − B平衡?A + B
空集 {}000✓0
{1} (1,1)110✓2
{5} (5,7)57−2✗—
{1,5}68−2✗—
{2,4} (2,3) + (8,2)105+5✗—
{1,4} (1,1) + (8,2)93+6✗—
{1,2,3,4,5} 全选2214+8✗—
1
为什么答案只有 2?

单件:(1,1) 差 0 平衡;(2,3) 差 −1;(6,1) 差 +5;(8,2) 差 +6;(5,7) 差 −2

带第 1 件的两件组合:(1,1)+(2,3) → −1,(1,1)+(6,1) → +5,(1,1)+(8,2) → +6,(1,1)+(5,7) → −2

其余两件组合:(2,3)+(6,1) → +4,(2,3)+(8,2) → +5,(2,3)+(5,7) → −3,(6,1)+(8,2) → +11,(6,1)+(5,7) → +3,(8,2)+(5,7) → +4

三件及以上的组合共 16 种(10 + 5 + 1),逐一检查差值也都不为 0

所以只有"只选第 1 件"这一种非空平衡方案,和 = 1 + 1 = 2

✅ 2

2
差值背包视角

读完五件后,dp[0] 只有两条来源:空集(Σa = 0)与 {1}(Σa = 1)

其余任何选法都落不到差值 0 上

dp[0] = 1 → 答案 2 × 1 = 2 ✓

✅ 一致

🔑
这组样例在提醒你两件事:① 空集是合法方案,所以答案不会小于 0(当所有 aᵢ ≠ bᵢ 且凑不出平衡时,答案是 0);② 不要只看"单件能不能平衡",真正的最优解往往来自多件组合——样例 1 的答案 8 就来自两件食材的组合。
04
解法对比
差值背包 vs 二维 DP / 枚举子集

⚔️ 解法对比

🟢 差值背包(推荐) 推荐

把 (A, B) 压成差值 d = A − B,dp[d] 记录最大的 Σa

  • 时间 O(n × 100001) ≈ 10⁷
  • 空间 O(100001) 两个 int 数组
  • 代码约 25 行
  • 答案 = 2 × dp[偏移],天然处理空集
💡
转移怎么写:不选 → ndp 继承 dp;选 → ndp[d + aᵢ − bᵢ] = max(ndp[…] , dp[d] + aᵢ)。必须用双数组,因为差值可正可负,"倒序遍历"那招防不住重复选同一件。

🟠 二维 DP((A,B) 两维)

直接用 dp[A][B] 标记"酸度 A、甜度 B 可达"

  • 时间 O(n × 50000 × 50000)
  • 空间 2.5 × 10⁹ 个格子
  • ❌ 内存直接爆掉
  • 只有在 aᵢ, bᵢ ≤ 10 的部分分才勉强能用
⚠️
这正说明了"压维"的必要性:二维看起来最直观,但状态数 = (Σa 的上界) × (Σb 的上界),只有差值才把"乘法级"的状态压回了"加法级"。

📈 性能对比

方案复杂度代码量
差值背包O(n × 10⁵) ≈ 10⁷约 25 行
二维 DPO(n × (5 × 10⁴)²)❌ 空间爆炸
枚举所有子集O(2ⁿ) = 2¹⁰⁰❌ 不可能
05
算法流程图
差值背包的滚动更新
开始读入 n 与每件食材的 (aᵢ, bᵢ)dp[偏移] = 0,其余 dp[d] = −1(不可达);偏移 = 50000对第 i 件食材:先让 ndp = dp(不选它)差值 d 这个状态 dp[d] 可达吗?可达 ✓ndp[d + aᵢ − bᵢ] = max(ndp[d + aᵢ − bᵢ], dp[d] + aᵢ)(选它)不可达 ✗跳过,不产生转移(该差值暂时凑不出来)n 件食材、所有差值 d 都扫完了吗?输出 2 × dp[偏移]继续下一个 d
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

⚖️ 最大酸度 + 甜度之和

第一行输入 n,随后 n 行每行两个整数 a b(1 ≤ a, b ≤ 500)。程序用差值背包求解,并对 n ≤ 18 的情况用枚举子集给出具体选法。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码(差值背包)

#include <bits/stdc++.h>
using namespace std;

const int OFF = 50000;    // 偏移量:把差值 0 搬到下标 50000
const int SZ  = 100001;   // 差值取值范围 [−50000, +50000]
int dp[SZ], ndp[SZ];

int main() {
    int n;
    scanf("%d", &n);

    // dp[d] = 所选食材的"酸度 − 甜度"等于 (d − OFF) 时,最大的 Σa
    // 用 −1 表示"这个差值不可达"(因为所有可达的 Σa 都 ≥ 0,0 是合法值!)
    memset(dp, -1, sizeof(dp));
    dp[OFF] = 0;                          // 空集:差值 0,Σa = 0

    for (int i = 0; i < n; i++) {
        int a, b;
        scanf("%d %d", &a, &b);

        memcpy(ndp, dp, sizeof(dp));      // 选择一:不要这件食材
        int d0 = a - b;                   // 要它 → 差值增加 a − b
        for (int d = 0; d < SZ; d++) {
            if (dp[d] < 0) continue;      // 不可达状态跳过
            int t = d + d0;
            if (t < 0 || t >= SZ) continue;   // 越界兜底(理论上不会发生)
            if (dp[d] + a > ndp[t])       // 选择二:要它 → Σa 增加 a
                ndp[t] = dp[d] + a;
        }
        memcpy(dp, ndp, sizeof(dp));
    }

    // dp[OFF] 就是"Σa = Σb"时的最大 Σa,于是 A + B = 2 × Σa
    printf("%d\n", 2 * dp[OFF]);
    return 0;
}
🔑
为什么一定要用两个数组?0/1 背包常见的"原地倒序遍历"技巧在这里失效了:因为差值增量 aᵢ − bᵢ 可正可负,"新状态"可能在下标更大处、也可能在更小处,倒序根本挡不住"同一件被用两次"。
最稳妥的写法就是:ndp 先整体继承 dp(不选),再用 dp 推出所有"选"的转移,最后把 ndp 拷回 dp。

📖 关键几行怎么看

代码作用为什么这样写
dp[OFF] = 0;初始状态空集是最基本的平衡方案:A = B = 0
memset(dp, -1, …)不可达标记不能填 0——0 是合法的 Σa 值
memcpy(ndp, dp, …)不选的转移0/1 背包的"继承"分支
ndp[t] = max(ndp[t], dp[d] + a)选它差值 +(aᵢ − bᵢ),Σa + aᵢ
2 * dp[OFF]取答案平衡时 A = B,所以 A + B = 2A
⚠️
四个坑:① 不可达状态用 0 初始化(0 是合法值,会被误当成"可达且 Σa = 0");② 忘记偏移量 50000 → 出现负下标越界;③ 原地更新 → 同一件食材被重复选入;④ 差值上界开小(n × 500 = 50000,必须留足)。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
3
1 2
2 4
3 2
8题面样例 1
5
1 1
2 3
6 1
8 2
5 7
2题面样例 2
1
1 1
2单件且 a = b:选它就平衡,和 = 2
1
1 2
0单件不平衡 → 只能选空集,答案 0
2
2 1
1 2
6两件互补:Σa = Σb = 3,和 = 6
3
1 3
2 2
3 1
12三件全选:Σa = Σb = 6,和 = 12
4
1 2
2 4
3 2
5 5
18选 (1,2)+(3,2)+(5,5):Σa = Σb = 9
✅
自查清单:① 数组开 100001、偏移 50000 吗?② 用 −1 标记不可达吗?③ 用 ndp 双数组吗?④ 输出的是 2 × dp[OFF] 吗?

🚨 易错点清单

⚠️
不可达状态初始化成 0:0 是合法的 Σa,必须用 −1 表示"不可达"。
⚠️
原地更新 dp:差值可正可负,倒序遍历防不住重复选,必须用 ndp 双数组。
⚠️
忘记偏移量:差值为负会下标越界,统一加 50000。
⚠️
以为必须选至少一件:空集是合法平衡方案,答案至少是 0。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n × 100001) ≈ 10⁷
空间复杂度
O(100001)
差值上界
±50000 = ±(n × 500)
答案上界
100000 = 2 × 100 × 500

时间怎么算的?

空间都用在哪?

两个 int 数组:100001 × 4 B × 2 ≈ 800 KB,相对 256 MB 限制非常宽裕。

✅ 约一千万次操作,毫秒级完成。差值上界 50000 的来历:每件食材的差值最多 499(因为 aᵢ, bᵢ ≤ 500),100 件最多累积到约 50000,所以数组开到 100001 一定够用。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 差值背包的核心:把 (Σa, Σb) 两维压成"差值"一维
// dp[d + OFF] = 选出的食材满足 Σa − Σb = d 时,最大的 Σa
for (int i = 0; i < n; i++) {
    memcpy(ndp, dp, sizeof(dp));                  // 不选第 i 件
    for (int d = 0; d < SZ; d++) {
        if (dp[d] < 0) continue;
        int t = d + a[i] - b[i];                  // 选第 i 件:差值变化
        if (ndp[t] < dp[d] + a[i]) ndp[t] = dp[d] + a[i];
    }
    memcpy(dp, ndp, sizeof(dp));
}

// 变体 1:求"平衡方案的最少件数" → dp 存最小件数,答案取 dp[OFF]
// 变体 2:求"平衡方案数"        → dp 存方案数(long long),转移改加法
// 变体 3:只问"能否平衡"        → dp 改 bool,可用 bitset 位运算加速
// 变体 4:aᵢ, bᵢ 很大(如 10⁹)→ 差值范围爆炸,改用哈希表存可达状态

// 通用心法:两个约束维度 → 常能压成一个"差/比值"维度

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
差值压缩把 (Σa, Σb) 两维压成 d = Σa − Σb天平配重、双指标平衡、股票差价类问题
偏移量技巧差值可为负 → 统一加 50000一切需要"负数下标"的数组 DP
0/1 背包双数组ndp 继承 + 转移,再整体拷回差值可正可负时防止重复选
可达性 × 最优化dp 存最大值,用 −1 区分不可达求极值的 DP(牢记 0 是合法值)
🌟
思考题:如果题目改成"必须至少选一件食材且平衡",答案会变吗?(提示:只要 aᵢ, bᵢ 都是正整数,能凑出和为 0 的平衡方案就只有空集,所以答案不变;但如果允许 aᵢ = bᵢ = 0 的食材存在,就会出现"和同样为 0 的非空方案",此时需要额外加一维标记"是否已选过",才能真正区分)。