首页
登录 | 注册

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

[问题背景]

蓝桥杯 历届试题 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 大嘛?)



2020 jeepxie.net webmaster#jeepxie.net
10 q. 0.008 s.
京ICP备10005923号