daily

用户名：weightless

访问量：1171

签　名：

Hello world！

等　　级
排　　名	10905
经　　验	1001
参赛次数	5
文章发表	2
年　　龄	15
在职情况	学生
学　　校	绍兴鲁迅中学
专　　业

　　自我简介：

热爱计算机，目前正处于入门阶段（QQ号 3205177338）

TA的其他文章

最大体积（动态规划补空隙C++）
浏览：386

你可能喜欢

C语言程序设计教程（第三版）课后习题8.3 （Java代码）

最大体积（动态规划补空隙C++）

　　作者: daily　　　　发表时间：2022-02-09 09:56:32 浏览：386　|　评论：4　

原题链接：蓝桥杯算法训练VIP-最大体积

1. - 分析问题
首先，由扩展欧几里得算法，可以得出若x,y为正整数a,b为整数，**则ax+by=1有解是x与y互质的充要条件。**
所以当给出的体积互质时（所有体积的最大公约数为1），一定有解；反之无解。
由此，可以先计算所有给出体积的最大公约数，判断是否有解，确定有解后进行下一步计算。于是定义了函数gcd和haveanswer两个函数，在haveanswer中调用gcd，来计算所有给出体积的最大公约数。返回最大公约数x==1的布尔值，有解情况下即返回true。
如果有解，下一步，分析如何进行动态规划。以样例为例，3,6,10三个体积，用可能组成的体积作为i，取的物体的数量作为j，dp[i][j]表示取j个物体时是否能组成体积i（布尔值）。得到：
>j=1时，dp[3,6,10][1] = 1;
j=2时，dp[3,6,9,12,13,16,20][2] = 1;
j=3时，dp[3,6,9,12,13,15,16,18,19,20,22,23,26,30][3] = 1;

没必要再往下了。由18,19,20，三个连续的数字，我们发现18+3=21,19+3=22,20+3=23,21+3=24,22+3=25...如此像履带一样像前碾压，后面的所有体积将会被组成，由此得到不能组成的最大体积为17，于是得到：
>当该问题有解时，视给出的最小体积为最小空隙，由动态规划得到的第一次能组成的连续体积个数等于给出的最小体积时，最小空隙被填补，于是后面所有体积都可以组成，这组连续体积中最大的体积减去给出的最小体积即为不能组成的最大体积。

- 参考代码

```cpp
#include<iostream>
#define MAX 200000001
using namespace std;
bool dp[MAX];

int min(int n, int a[]) { //找出最小空隙
	int m = a[0];
	for(int i = 1; i < n; i++)
		if(a[i] < m)
			m = a[i];
	return m;
}

int gcd(int a, int b) {  //最大公约数
	return b == 0 ? a : gcd(b, a % b);
}

bool haveanswer(int n, int a[]) {  //计算是否有解
	int x = gcd(a[0], a[0]);  //这样是为了防止数组越界
	for(int i = 1; i < n; i++) {
		x = gcd(a[i], x);
	}
	return x == 1;
}

int main() {
	int n, *a, maxv = 0;  //记录下给出的最大的体积 
	scanf("%d", &n);
	a = new int[n];
	for(int i = 0; i < n; i++) {
		scanf("%d", a + i);
		dp[a[i]] = 1;  //标记下原有体积 
		maxv = a[i] > maxv ? a[i] : maxv;
	}
	if(!haveanswer(n, a)) {
		printf("%d", 0);
		return 0;
	}
	int ans = 0, minsep = min(n, a), answer = 0, i = minsep - 1;  //ans:连续体积的个数;minsep:最小空隙;answer:答案;i:递增体积 
	while(++i) {
		if(dp[i]) {
			ans++;
			if(ans == minsep) {  //找到啦！！！ 
				answer = i - minsep;
				break;
			}
			for(int j = 0; j < n; j++) {
				dp[i + a[j]] = 1;
			}
		} else
			ans = 0;
	}
	if(answer >= MAX)  //超出范围视作无解 
		answer = 0;
	printf("%d", answer);
	return 0;
}
```
PS：请多指教，感谢阅读！！！

0.0分

42 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

　　评论区

BITxiaohao

开个两亿的空间？

2022-11-22 18:21:28

violinwang

不超时的前提 是不是 这个不能表示的最大的数字 不能太大，而且是肯定不能达到题目中的有限解上限？
那这个 解  的范围是不是在本题中是一定的？

2022-02-19 19:58:18

violinwang

这是人能想出来的吗？！tql

2022-02-19 19:50:02

流氓抠脚

真TM的好

2022-02-09 23:09:18

daily

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.3 （Java代码）

人见人爱A+B （C++代码）

Hello, world! （C语言代码）

C二级辅导-阶乘数列（C++代码）

【明明的随机数】（C语言代码）

最大体积（动态规划补空隙C++）

评论区

精彩推荐

A+B for Input-Output Practice (VI) （C语言代码）

gets函数前有scanf读取时候，会读取缓存回车导致出错！！！

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

数组输出（C语言代码）--此题的题目描述有问题

WU-蓝桥杯算法提高VIP-勾股数（C++代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

wu-理财计划（C++代码）

WU-C语言程序设计教程（第三版）课后习题11.11 （C++代码）（想学链表的可以看看）

用筛法求之N内的素数。（C语言代码）

1157题解

daily

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.3 （Java代码）

人见人爱A+B （C++代码）

Hello, world! （C语言代码）

C二级辅导-阶乘数列 （C++代码）

【明明的随机数】 （C语言代码）

最大体积（动态规划补空隙C++）

评论区

精彩推荐

A+B for Input-Output Practice (VI) （C语言代码）

gets函数前有scanf读取时候，会读取缓存回车导致出错！！！

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

数组输出 （C语言代码）--此题的题目描述有问题

WU-蓝桥杯算法提高VIP-勾股数 （C++代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

wu-理财计划 （C++代码）

WU-C语言程序设计教程（第三版）课后习题11.11 （C++代码）（想学链表的可以看看）

用筛法求之N内的素数。 （C语言代码）

1157题解

C二级辅导-阶乘数列（C++代码）

【明明的随机数】（C语言代码）

　　评论区

数组输出（C语言代码）--此题的题目描述有问题

WU-蓝桥杯算法提高VIP-勾股数（C++代码）

wu-理财计划（C++代码）

用筛法求之N内的素数。（C语言代码）