买不到的数字

李超2024年12月26日大约 6 分钟教学文档动态规划

买不到的数字（动态规划）

1. 题目描述

小明开了一家糖果店。他别出心裁：把水果糖包成 4 颗一包和 7 颗一包的两种。糖果不能拆包卖。小朋友来买糖的时候，他就用这两种包装来组合。当然有些糖果数目是无法组合出来的，比如要买 10 颗糖。你可以用计算机测试一下，在这种包装情况下，最大不能买到的数量是 17。大于 17 的任何数字都可以用 4 和 7 组合出来。

本题的要求就是在已知两个包装的数量时，求最大不能组合出的数字。

2. 分析

要解决这一个问题，我们可以用动态规划的思路：

首先我们使用一个数组 dp 来表示能够组合出的糖果数量，dp[i] 表示能否组合出数量为 i 的糖果。使 dp[0] = true（因为不买任何糖果也是一种组合方式，即组合出数量为 0 的糖果。）其他 dp[i] 初始化为 false，表示一开始不能组合出这些数量的糖果。

遍历每个可能的糖果数量 i，从 1 到一个合理的上限（比如两个包装数量的乘积的若干倍，考虑到糖果数量不会太大，我们可以选择一个合适的上限）。对于每个 i，检查是否可以通过加上一个包装的数量（4 或 7）从之前的状态转移而来。如果 dp[i - 4] 为 true，则 dp[i] 也为 true（假设当前包装有 4 颗糖果）。同理，如果 dp[i - 7] 为 true，则 dp[i] 也为 true（假设当前包装有 7 颗糖果）。

最后遍历 dp 数组，找到最后一个 false 的位置，这个位置就是最大不能组合出的数字。

3. 代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    // 取两个包装数量的最大值作为上限的初步估计
    int max_value = max(a, b) * 50; // 50 是一个经验值，可以根据实际情况调整
    // 动态规划数组，dp[i] 表示能否组合出数量为 i 的糖果
    vector<bool> dp(max_value + 1, false);
    dp[0] = true; // 初始化，组合出 0 颗糖果是可能的
    // 状态转移
    for (int i = 1; i <= max_value; ++i) {
        if (i >= a && dp[i - a]) {
            dp[i] = true;
        }
        if (i >= b && dp[i - b]) {
            dp[i] = true;
        }
    }
    // 找到最后一个 dp[i] 为 false 的位置
    for (int i = max_value; i >= 0; --i) {
        if (!dp[i]) {
            cout << i << endl;
            break;
        }
    }
    return 0;
}

问题：如果上限设得太小（如仅设为 max(a, b) * 2），可能无法覆盖真正的最大不可表示数。
解决方案：利用数论结论——当 a 和 b 互质时，最大不可表示数为 ab - a - b，因此设 limit = a * b 是安全的。
验证：对于 a=4, b=7，理论最大值为 4×7-4-7=17，而 limit=28 足够覆盖。

2. 输入数据的互质性假设

问题：如果 gcd(a, b) > 1，则有无穷多个数无法表示（所有非 gcd 倍数的数），此时“最大不可表示数”不存在。
题目保证：题目说明“不需要考虑无解的情况”，隐含输入的两个数互质，但实际编程中最好验证 gcd(a,b)==1。

3. 边界条件处理

dp[0] = True：0颗糖是基础情况，必须初始化为 True，否则后续状态无法转移。
数组越界：在检查 dp[i-a] 和 dp[i-b] 前，必须确保 i >= a 或 i >= b。

4. 空间和时间复杂度的权衡

空间开销：当 a 和 b 接近 1000 时，limit = 10^6，需要 1MB 左右的布尔数组，在现代计算机上可接受。
优化可能：可使用滚动数组或只记录最近 max(a,b) 个状态，但会增加代码复杂度。

5. 结果查找的正确性

必须从高到低查找：要找的是“最大”的不可表示数，所以从 limit 向下遍历，找到第一个 False 即可返回。

二、解决该问题的启发

1. 数学理论与算法实现的结合

启发：虽然可以用纯动态规划解决，但了解背后的数学原理（Frobenius 数）能帮助我们：
- 正确设置算法边界（limit = a*b）
- 验证结果正确性
- 在某些场景下直接使用公式 a*b - a - b 获得 O(1) 解法
应用：在算法设计中，数学洞察力往往能大幅提升效率和正确性。

2. 动态规划的状态定义要精准

状态定义：dp[i] 表示“能否恰好组成 i 颗糖”，这是一个典型的可行性 DP。
状态转移：dp[i] = dp[i-a] or dp[i-b]，体现了“只要有一种方式能到达当前状态即可”。
启发：对于组合/拆分类问题，通常定义 dp[i] 为“能否达到目标 i”是有效的思路。

3. 问题规模分析的重要性

关键洞察：“一旦连续出现 min(a,b) 个可表示的数，之后的所有数都可表示”。
优化方向：实际上不需要计算到 a*b，只需找到连续 min(a,b) 个 True 的起始位置即可停止。

代码改进：

consecutive = 0
for i in range(1, some_upper_bound):
    # ... dp update ...
    if dp[i]:
        consecutive += 1
        if consecutive == min(a, b):
            break
    else:
        consecutive = 0
        last_impossible = i

4. 通用性与特殊性的平衡

通用解法：DP 方法适用于任意数量的包装规格（如 3 种、4 种包装），而公式 ab-a-b 仅适用于两种互质数。
启发：当问题可能扩展时（如增加更多包装类型），选择通用算法比依赖特殊公式更有前瞻性。

5. 测试用例设计的思考

边界测试：a=1, b=任意（此时所有数都可表示，最大不可表示数为 -1，但题目保证有解）
典型测试：a=3, b=5 → 答案应为 3×5-3-5=7
大数测试：a=999, b=1000 → 验证性能和正确性

三、总结

这个问题完美展示了算法设计中理论与实践的结合：

理论层面：数论提供了问题的性质和边界
实践层面：动态规划提供了通用、可靠的求解框架
工程层面：需要考虑效率、边界、可扩展性等实际因素

通过这类问题的训练，我们不仅能掌握动态规划技巧，更能培养“用数学思维指导算法设计”的能力，这在解决复杂工程问题时尤为宝贵。

买不到的数字

买不到的数字（动态规划）

1. 题目描述

输入描述

输出描述

样例

样例输入

样例输出