小明买糖，C语言编程

Question

题目描述
小明开了一家糖果店。他别出心裁：把水果糖包成4颗一包和7颗一包的两种。糖果不能拆包卖。
小朋友来买糖的时候，他就用这两种包装来组合。当然有些糖果数目是无法组合出来的，比如要买 10 颗糖。
你可以用计算机测试一下，在这种包装情况下，最大不能买到的数量是17。大于17的任何数字都可以用4和7组合出来。
本题的要求就是在已知两个包装的数量时，求最大不能组合出的数字。
输入
两个互质的正整数，表示每种包装中糖的颗数(都不多于1000)
输出
一个正整数，表示最大不能买到的糖数

Answer 1

【以下回答由 GPT 生成】

解决方案：

由于本题需要计算最大不能买到的糖数，可以采用贪心算法的思想来解决。具体步骤如下：

1. 首先，我们需要找到给定两种包装下的最小包装数和最大包装数。
2. 最小包装数为两种包装中较小的数。

3. 最大包装数为两种包装中的较大数减去一个最小包装数。

4. 创建一个长度为最大包装数的布尔数组dp，用于标记能否达到该数字。

5. 初始化dp数组，将第一个标记位置为true。

6. 遍历从最小包装数到最大包装数的每个数字i：

7. 判断前一个数字i减去第一种包装数(j)是否能达到或者前一个数字i减去第二种包装数(k)是否能达到。

8. 如果能达到，将dp[i]标记为true。

9. 遍历dp数组，找到第一个标记为false的位置，即为最大不能买到的糖数。

下面是C语言的代码实现：

#include <stdio.h>

int main() {
    int pack1, pack2;

    printf("请输入两种包装中糖的颗数（用空格分隔）：");
    scanf("%d %d", &pack1, &pack2);

    int minPack = (pack1 < pack2) ? pack1 : pack2;
    int maxPack = ((pack1 > pack2) ? pack1 : pack2) - minPack;

    int dp[maxPack + 1];
    dp[0] = 1;

    for (int i = 1; i <= maxPack; i++) {
        if (i >= pack1 && dp[i - pack1]) {
            dp[i] = 1;
        } else if (i >= pack2 && dp[i - pack2]) {
            dp[i] = 1;
        } else {
            dp[i] = 0;
        }
    }

    int ans = 0;
    for (int i = maxPack; i >= 0; i--) {
        if (!dp[i]) {
            ans = i;
            break;
        }
    }

    printf("最大不能买到的糖数为：%d\n", ans);

    return 0;
}

运行结果示例：

请输入两种包装中糖的颗数（用空格分隔）：4 7
最大不能买到的糖数为：17

注意事项： - 输入的两种包装中糖的颗数要求是互质的正整数，否则可能会导致计算结果不正确。 - 这里的解决方案使用了动态规划的思想，通过一个布尔数组记录状态，时间复杂度为O(n)，其中n为最大包装数。

【相关推荐】

• 帮你找了个相似的问题, 你可以看下: https://ask.csdn.net/questions/7705489
• 除此之外, 这篇博客: 学习C语言从小白到专家你只需要这一篇博客-史上最全C语言学习资源整理中的 答：是坚持，是行动。不是你存满一个收藏夹的文章，放满一个硬盘的资源就结束了的，那反而会加大一个人的焦虑，所以时常清理一下自己的收藏夹，做事，做少事，但要做精！这也是我这里并没有像其他教程那样给你推个几十个课程，几十本书，那没有意义，沉淀下来，别被现在的浮夸风给影响了，克服一下自己的松鼠症，千里之行始于足下，心怀大志但要脚踏实地，各位，加油！ 部分也许能够解决你的问题。

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^