C/C++百题打卡[9/100]——砝码称重[3种解法、蓝桥杯2021省赛]

关键字：蓝桥杯2021省赛、砝码称重[3种解法]、运行结果比较。

文章共3,778字 · 阅读需要大约13分钟

一键AI生成摘要，助你高效阅读

问答

一支王同学

6365人浏览 · 2022-03-17 11:38:24

一支王同学 · 2022-03-17 11:38:24 发布

✅

文章目录

一、题目总述
二、题目解析 + 完整代码
三、运行结果比较
四、做题小结与感慨
五、参考附录

上一题链接: C/C++百题打卡[8/100]——七段码[不用dfs的题解、蓝桥杯2020省赛].
百题打卡总目录： 🚧 🚧 …

一、题目总述

在这里插入图片描述
◆ 运行限制：
最大运行时间：1s
最大运行内存：256M

● 题目难度：⭐️⭐️⭐️⭐️⭐️

二、题目解析 + 完整代码

● 解法一：数据结构(队列queue) + 算法(bfs)

● 解法二：数据结构(普通数组) + 算法(动态规划)

● 解法三：数据结构(集合set + 数组vector) + 算法(无)

● 首先说 解法一：数据结构(队列queue) + 算法(bfs)。这也是我最先想到的，后面两种都是看了别人的思路后，自己重写的一遍。算法步骤：
[1] 初始化一个装 int 变量的队列Q。
[2] 每输入一个新的砝码 w，计算这个 w 与队列 Q 里面所有的 已有的重量 的 和 与 差，如果 计算出来的值 是一个新的 重量(队列中没有)，就装进去。
[3] 值得一提的是，不仅要装上一步中 符合要求的重量，还要再装一遍 Q中每一个已有的重量 。
[4] 还有就是，我们在实际编程中还需要另外一个临时队列 tmp_Q，至于为什么参见代码注释。

◆ 对 [3] 的解释：因为对于题目中的样例而言，有 3 个砝码(1, 4, 6)，没有 [3] 的话，就不可能出现 “7=1+6” 的情况。

#include<iostream>
#include<queue>
#include<cmath>
using namespace std;

queue<int> Q;
int N;
int w;
int cnt;
bool ans[1000010];

int main()
{
	cin >> N;
	Q.push(0);
	for (int i = 0; i < N; i++)
	{
		cin >> w;
		queue<int> tmp_Q;
		while (!Q.empty())
		{
			int tmp = Q.front();
			Q.pop();
			if (ans[tmp + w] == false)		// 左边加新的砝码
			{
				ans[tmp + w] = true;
				cnt++;		// 答案数+1
				tmp_Q.push(tmp + w);
			}
			if (ans[abs(tmp - w)] == false)	// 右边加新的砝码
			{
				ans[abs(tmp - w)] = true;
				cnt++;		// 答案数+1
				tmp_Q.push(abs(tmp - w));
			}
			tmp_Q.push(tmp);	// 重装一遍 Q 里的每一个“元素”
		}
		Q = tmp_Q;	// 执行到这里的时候, Q 已经为空了, 重新赋值一遍.
					// 如果没有 tmp_Q, 即前面的 tmp_Q 全部换成 Q, 那么 while() 循环就一直跳不出来!
	}
	if (ans[0] == true)	
		cout << cnt - 1 << endl;	// 重量为 0 的情况不要
	else
		cout << cnt << endl;
	return 0;
}

● 其次说 解法二：数据结构(普通数组) + 算法(动态规划)。感觉能想到这种思路的话，那可能对 “背包问题” 有一定的见解。算法步骤：
[1] 初始化一个 bool 类型的普通数组 a[i][j]，i 代表的是“装入前 i 个砝码”，j 代表的是“重量j”，a[i][j] 代表的是 “装入前 i 个砝码后，能否凑成重量为 j 的情况，能凑成的话，值就为 true，否则为 false”。
[2] 有 N 个砝码，就遍历 N 遍，每遍装入一个新的砝码。在每次遍历中要做 [3] 和 [4] 两件事。
[3] 首先，继承上一轮的结果。因为对于 “前 i 个砝码能凑成的所有重量的集合” ，那么前 i+1 个砝码一定也能凑到。
[4] 然后遍历继承上一轮结果的 a[i][j](只有 j 在变)，然后我们就去看，在 a[i][j] ==false 的情况下，是否能通过某种手段(代码中的三种)使得 a[i][j] 变为 true。

#include<iostream>
#include<cmath>
using namespace std;

int N;
int a[101];
int cnt;
bool ans[101][1000010];

int main()
{
	cin >> N;
	int tol = 0;

	for (int i = 1; i <= N; i++)	
	{
		cin >> a[i];
		tol += a[i];	
	}

	for (int i = 1; i <= N; i++)
	{
		// 继承上一轮的结果。因为对于 “前 i 个砝码能凑成的所有重量的集合”, 则前 i+1 个砝码一定也能凑到
		for (int j = 1; j <= tol; j++)	
			ans[i][j] = ans[i - 1][j];

		for (int j = 1; j <= tol; j++) 	// 只需要遍历到 tol
		{
			if (ans[i][j] == false)
			{
				if (a[i] == j)		// 手段一：新加入砝码的重量 正好为 j
					ans[i][j] = true;
				else if (ans[i-1][j + a[i]] == true)		// 手段二(背包的思想)
					ans[i][j] = true;
				else if (ans[i-1][abs(j - a[i])] == true)	// 手段三(背包的思想)
					ans[i][j] = true;
			}
		}
	}
	for (int i = 1; i <= tol; i++) // 从重量为 1 的情况开始计数
	{
		if (ans[N][i] == true)		// 对于前 N 个砝码, 能凑成重量为 i 的情况的话, 计数就 + 1
			cnt++;
	}
	cout << cnt << endl;
	return 0;
}

● 最后说 解法三：数据结构(集合set + 数组vector) + 算法(无)。感觉要用这种方法的话，那可能得对 “数据结构” 有一定的见解，但是一想到就很简单！。算法步骤：
[1] 初始化一个装 int 类型的变量的集合 set，因为 set 自带 “去重” 的功能，那么它就为我们省去了很多关于 “判断” 的事。
[2] 和 解法一 类似，我们需要用一个临时的中间容器 数组verctor 来辅助，原因详见代码。

#include<iostream>
#include<vector>
#include<set>
#include<cmath>
using namespace std;
int N;
int w;
set<int> s;
int main()
{
	cin >> N;
	for (int i = 1; i <= N; i++)
	{
		cin >> w;
		vector<int> v(s.begin(), s.end());	
		for (int i = 0; i < v.size(); i++)	// 如果没有 v, 即前面的 v 全部换成 s, 那么 for() 循环就一直跳不出去!
		{
			s.insert(w + v[i]);
			if( abs(w - v[i])!=0 )	 		// 我们不要 组合重量为 0 的情况
				s.insert(abs(w - v[i]));
		}
		s.insert(w);
	}
	cout << s.size() << endl;	// 集合 s 中装了不同的 “组合重量” 的数量即是答案
	return 0;
}