[算法提高] 动态规划买不到的数目

ゝ一纸荒年。 2022-03-02 05:06 126阅读 0赞

**\[问题背景\]**

[蓝桥杯 历届试题 PREV-8 买不到的数目][_ PREV-8]

问题描述

小明开了一家糖果店。他别出心裁：把水果糖包成4颗一包和7颗一包的两种。糖果不能拆包卖。

小朋友来买糖的时候，他就用这两种包装来组合。当然有些糖果数目是无法组合出来的，比如要买 10 颗糖。

你可以用计算机测试一下，在这种包装情况下，最大不能买到的数量是17。大于17的任何数字都可以用4和7组合出来。

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

输入格式

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

输出格式

一个正整数，表示最大不能买到的糖数

样例输入1

4 7

样例输出1

17

样例输入2

3 5

样例输出2

7

**\[思路分析\]**

考虑一下，记两个正整数分别为a和b，且a  < b，待组合的为i。

能被a和b组合出的 i 只有这样几种可能：

可能一：全部由a组成：记为x(a)

可能二：全部由b组成：记为y(b)

可能三：既有a，又有b：显然，如果a个数比b个数多，那么有x(a+b) + y(a); 如果b个数比a个数多，那么有x(a+b) + y(b)

对于几种可能的判定：

可能一：i % a == 0 为 true

可能二：i % b == 0 为 true

可能三：将 i 不断减去(a+b)，总会转化为可能一或者可能二。（此处递归）

另外，当 i = a + b时，减去(a+b)会变成0，这个点注意一下。

不满足能被a和b组合的数可以记为m = x(a+b)+c，其中0 < c < a+b, x = m / (a+b), c = m % (a+b)

这个数不断减去(a+b)，最终 m - x(a+b) = c, 0 < c < a+b

这时看c能否转化为可能一或者可能二，如果还不能，则再减一次(a+b)，c就为负数，那么c就无法转化为可能一或者可能二，这时的m就是无法被a和b组合的数，输出false

**\[代码求解\]**

#include <iostream>
    using namespace std;
    bool iscapable(int i, int a, int b) {
    	if (i < 0) 
    		return false;
    	if (i % a == 0 || i % b == 0 || i == (a+b)) {
    		return true;
    	}else{
    		i -= (a + b);
    		return iscapable(i, a, b);
    	}
    }
    int main () {
    	int a, b;
    	cin >> a >> b;
    	for (int i = a * b - 1; i > max(a,b); i--) {
    		if (!iscapable(i, a, b)) {
    			cout << i;
    			break;
    		}
    	}
    	return 0;
    }

以下是三个官方测试点：

input1

10 13

input2

30 41

input3

257 191

**\[方法总结\]**

可能算不上动态规划，大概属于分类剪枝。。。有空我再研究研究

没有解决的空白是：

是否存在这样的数m, m > a\*b， 且m不属于上述三种可能？（这个组合不了的数会比 a\*b 大嘛？）

[_ PREV-8]: http://lx.lanqiao.cn/problem.page?gpid=T31

发表评论取消回复

表情：

评论列表（有 0 条评论，126人围观）

还没有评论，来说两句吧...

相关阅读

相关【算法】【动态规划】买股票的最佳时机

121 [买卖股票的最佳时机 - 买卖股票的最佳时机 - 力扣（LeetCode）][- _ - _LeetCode] //版本一 class S

深藏阁楼爱情的钟/ 2024年04月05日 07:21/ 0 赞/ 43 阅读

相关买不到的数目

买不到的数目小明开了一家糖果店。他别出心裁：把水果糖包成4颗一包和7颗一包的两种。糖果不能拆包卖。小朋友来买糖的时候，他就用这两种包装来组合。当然有些糖

阳光穿透心脏的1/2处/ 2024年03月30日 16:07/ 0 赞/ 27 阅读

相关【蓝桥杯】买不到的数目

[1205. 买不到的数目 - AcWing题库][1205. _ - AcWing] 题意： ![bddfe8f899fd484cb426739f1b4f75b3.png

系统管理员/ 2024年03月30日 10:18/ 0 赞/ 29 阅读

相关 13省Ca8-买不到的数目！！

问题描述小明开了一家糖果店。他别出心裁：把水果糖包成4颗一包和7颗一包的两种。糖果不能拆包卖。小朋友来买糖的时候，他就用这两种包装来组合。当然有些糖果数目是无法组合

墨蓝/ 2023年01月10日 11:53/ 0 赞/ 96 阅读

相关买不到的数目

小明开了一家糖果店。他别出心裁：把水果糖包成4颗一包和7颗一包的两种。糖果不能拆包卖。小朋友来买糖的时候，他就用这两种包装来组合。当然有些糖果数目是无法组合出

冷不防/ 2022年08月08日 13:55/ 0 赞/ 104 阅读

相关买苹果---动态规划

题目描述小易去附近的商店买苹果，奸诈的商贩使用了捆绑交易，只提供6个每袋和8个每袋的包装(包装不可拆分)。可是小易现在只想购买恰好n个苹果，小易想购买尽量少的袋数方便

﹏ヽ暗。殇╰゛Y/ 2022年06月09日 09:47/ 0 赞/ 118 阅读

相关蓝桥杯训练历届试题买不到的数目（猜公式）

问题描述小明开了一家糖果店。他别出心裁：把水果糖包成4颗一包和7颗一包的两种。糖果不能拆包卖。小朋友来买糖的时候，他就用这两种包装来组合。当然有些糖果数目是无法组合出来

绝地灬酷狼/ 2022年03月08日 09:22/ 0 赞/ 175 阅读

相关 [算法提高] 动态规划爬楼梯

\[问题背景\] 来源：LeetCode(力扣) 编号：[70. 爬楼梯][70.] 内容：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或

喜欢ヅ旅行/ 2022年03月06日 04:03/ 0 赞/ 189 阅读

相关 [算法提高] 动态规划买不到的数目

\[问题背景\] [蓝桥杯历届试题 PREV-8 买不到的数目][_ PREV-8] 问题描述小明开了一家糖果店。他别出心裁：把水果糖包成4颗一包和7颗一包的两种。糖

ゝ一纸荒年。/ 2022年03月02日 05:06/ 0 赞/ 127 阅读

相关 [算法提高] 动态规划 0-1背包问题

考虑一般性的0-1背包问题，设背包容量为c，物品数量为n，每件的物品都有自己的重量和价值，每件物品只有两种状态：放入(记为1)、不放入(记为0)，试寻找最优解满足放入的物品总重

逃离我推掉我的手/ 2022年02月15日 11:32/ 0 赞/ 178 阅读