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

1. 题目描述

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

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

输入描述

输入两个正整数，表示每种包装中糖的颗数(都不多于 1000 )。

输出描述

输出一个正整数，表示最大不能买到的糖数。
不需要考虑无解的情况。

样例

样例输入

4 7

样例输出

17

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;
}

4. 运行结果

在这个代码运行完成后，运行结果如下：