每种食材选或不选,在酸度和 = 甜度和的前提下,让两者之和最大。
小 A 有 n 种食材,第 i 种食材的酸度为 aᵢ、甜度为 bᵢ。每种食材可以选入料理,也可以不选。
料理的酸度 A 是所选食材酸度之和,甜度 B 是所选食材甜度之和。若 A = B,则称调味平衡。在保证平衡的前提下,求 A + B 的最大值。
Σa = Σb,并让 Σa + Σb 尽量大。Σa = Σb,所以目标等价于让 Σa 尽量大(答案就是 2 × Σa)。差值背包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 |
dp[A][B] 记录"酸度 A、甜度 B 是否可达",A、B 各可达 50000,二维数组要 50000 × 50000 = 2.5 × 10⁹ 个格子,时间和空间都爆炸dp[d] = 差值为 d 时最大的 Σa,平衡条件就变成了单一目标 d = 0n = 3,一共只有 2³ = 8 种选法,先把它们全部列出来。
| 选法 | 酸度 A | 甜度 B | A = B ? | A + B |
|---|---|---|---|---|
| 空集 {} | 0 | 0 | ✓ 平衡 | 0 |
| {1} (1,2) | 1 | 2 | ✗ | — |
| {2} (2,4) | 2 | 4 | ✗ | — |
| {3} (3,2) | 3 | 2 | ✗ | — |
| {1,2} | 3 | 6 | ✗ | — |
| {1,3} | 4 | 4 | ✓ 平衡 | 8 |
| {2,3} | 5 | 6 | ✗ | — |
| {1,2,3} | 6 | 8 | ✗ | — |
只有 {1,3} 平衡,A + B = 4 + 4 = 8 ✓
初始: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
✅ 与枚举一致
食材为 (1,1)、(2,3)、(6,1)、(8,2)、(5,7)。这次有 2⁵ = 32 种选法,我们用"差值"的眼光看:
| 选法 | 酸度 A | 甜度 B | 差值 A − B | 平衡? | A + B |
|---|---|---|---|---|---|
| 空集 {} | 0 | 0 | 0 | ✓ | 0 |
| {1} (1,1) | 1 | 1 | 0 | ✓ | 2 |
| {5} (5,7) | 5 | 7 | −2 | ✗ | — |
| {1,5} | 6 | 8 | −2 | ✗ | — |
| {2,4} (2,3) + (8,2) | 10 | 5 | +5 | ✗ | — |
| {1,4} (1,1) + (8,2) | 9 | 3 | +6 | ✗ | — |
| {1,2,3,4,5} 全选 | 22 | 14 | +8 | ✗ | — |
单件:(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
读完五件后,dp[0] 只有两条来源:空集(Σa = 0)与 {1}(Σa = 1)
其余任何选法都落不到差值 0 上
dp[0] = 1 → 答案 2 × 1 = 2 ✓
✅ 一致
把 (A, B) 压成差值 d = A − B,dp[d] 记录最大的 Σa
ndp 继承 dp;选 → ndp[d + aᵢ − bᵢ] = max(ndp[…] , dp[d] + aᵢ)。必须用双数组,因为差值可正可负,"倒序遍历"那招防不住重复选同一件。直接用 dp[A][B] 标记"酸度 A、甜度 B 可达"
| 方案 | 复杂度 | 代码量 |
|---|---|---|
| 差值背包 | O(n × 10⁵) ≈ 10⁷ | 约 25 行 |
| 二维 DP | O(n × (5 × 10⁴)²) | ❌ 空间爆炸 |
| 枚举所有子集 | O(2ⁿ) = 2¹⁰⁰ | ❌ 不可能 |
第一行输入 n,随后 n 行每行两个整数 a b(1 ≤ a, b ≤ 500)。程序用差值背包求解,并对 n ≤ 18 的情况用枚举子集给出具体选法。
点按钮开始 →
#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; }
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 |
写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
3 | 8 | 题面样例 1 |
5 | 2 | 题面样例 2 |
1 | 2 | 单件且 a = b:选它就平衡,和 = 2 |
1 | 0 | 单件不平衡 → 只能选空集,答案 0 |
2 | 6 | 两件互补:Σa = Σb = 3,和 = 6 |
3 | 12 | 三件全选:Σa = Σb = 6,和 = 12 |
4 | 18 | 选 (1,2)+(3,2)+(5,5):Σa = Σb = 9 |
2 × dp[OFF] 吗?两个 int 数组:100001 × 4 B × 2 ≈ 800 KB,相对 256 MB 限制非常宽裕。
✅ 约一千万次操作,毫秒级完成。差值上界 50000 的来历:每件食材的差值最多 499(因为 aᵢ, bᵢ ≤ 500),100 件最多累积到约 50000,所以数组开到 100001 一定够用。
// 差值背包的核心:把 (Σ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 是合法值) |