题目描述
小明开了一家糖果店。他别出心裁:把水果糖包成4颗一包和7颗一包的两种。糖果不能拆包卖。
小朋友来买糖的时候,他就用这两种包装来组合。当然有些糖果数目是无法组合出来的,比如要买 10 颗糖。
你可以用计算机测试一下,在这种包装情况下,最大不能买到的数量是17。大于17的任何数字都可以用4和7组合出来。
本题的要求就是在已知两个包装的数量时,求最大不能组合出的数字。
输入
两个互质的正整数,表示每种包装中糖的颗数(都不多于1000)
输出
一个正整数,表示最大不能买到的糖数
![](https://profile-avatar.csdnimg.cn/default.jpg!4)
小明买糖,C语言编程
- 写回答
- 好问题 0 提建议
- 追加酬金
- 关注问题
- 邀请回答
-
2条回答 默认 最新
关注
【以下回答由 GPT 生成】
解决方案:
由于本题需要计算最大不能买到的糖数,可以采用贪心算法的思想来解决。具体步骤如下:
- 首先,我们需要找到给定两种包装下的最小包装数和最大包装数。
- 最小包装数为两种包装中较小的数。
-
最大包装数为两种包装中的较大数减去一个最小包装数。
-
创建一个长度为最大包装数的布尔数组dp,用于标记能否达到该数字。
-
初始化dp数组,将第一个标记位置为true。
-
遍历从最小包装数到最大包装数的每个数字i:
- 判断前一个数字i减去第一种包装数(j)是否能达到或者前一个数字i减去第二种包装数(k)是否能达到。
-
如果能达到,将dp[i]标记为true。
-
遍历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语言学习资源整理中的 答:是坚持,是行动。不是你存满一个收藏夹的文章,放满一个硬盘的资源就结束了的,那反而会加大一个人的焦虑,所以时常清理一下自己的收藏夹,做事,做少事,但要做精!这也是我这里并没有像其他教程那样给你推个几十个课程,几十本书,那没有意义,沉淀下来,别被现在的浮夸风给影响了,克服一下自己的松鼠症,千里之行始于足下,心怀大志但要脚踏实地,各位,加油! 部分也许能够解决你的问题。
如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^本回答被题主选为最佳回答 , 对您是否有帮助呢?解决 无用评论 打赏 举报
悬赏问题
- ¥15 from seleniumwire import webdriver 在抓取http://链接的时候会自动转https://这个怎么解决
- ¥15 BAT根据上两级文件夹重新命名文件要求BAT
- ¥30 不会,学习,有偿解答
- ¥15 SQL查询语句报错(检查)
- ¥15 此表中公式应该怎么写
- ¥15 求HI-TECH PICC 9.50 PL3安装包
- ¥15 下载ctorch报错,求解
- ¥15 如何入门学习c语言,单片机
- ¥15 idea 编辑语言的选择
- ¥15 Windows下部署Asmjit