2021蓝桥杯B组 G题砝码称重

题目大意： 

 解法一：

首先想到的是可以用广度优先搜索的方式来进行暴力求解，通过使用递归来将每一种方法遍历，并且标记，不过由于此方法的时间复杂度是O(n3),故使用暴力搜索只能完成50%的评测用例，只能得一半的分。

代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6;
int vis[maxn];//记录每种称重是否出现过
int a[maxn];//N个砝码的重量
int N;//砝码的数量
void dfs(int sum, int i)//sum：当前已选用砝码的总重量 i：下一个将要选用砝码的序号
{
	if (i == N)
	{
		if (sum >= 0)
			vis[sum] = 1;
		return;
	}
	dfs(sum + a[i], i + 1);//把a[i]放在右边
	dfs(sum, i + 1);      //不选a[i]
	dfs(sum - a[i], i + 1);//把a[i]放在左边
}
int main()
{
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> a[i];
	}
	dfs(0, 0);
	int ans = 0;
	for (int i = 1; i < maxn; i++)
	{
		if (vis[i])
			ans++;
	}
	cout << ans << endl;
	return 0;
}

解法二：

正确解法是使用动态规划的方法，时间复杂度可以降低到O(n2)，提到动态规划典型的就是0-1背包问题，而本题可以看成是两个0-1背包问题。一方面是不放和往天平的右边放（加），另一方面是不放和往天平的左边放（减）。不过相比解法一，该代码理解起来比较难，首先，为了减少时间复杂度，我么需要用一个一维数组来存表，而且为了不重复使用之间用过的砝码，需要逆向填表。

关于将背包问题从二维转一维的具体思路和方法可以看该博客：https://elainelv.blog.csdn.net/article/details/79482477

代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[100005];//表示重量为j的称重能不能实现，取值为1或0
ll w[105];//N个砝码的重量
int main()
{
	ll N;
	cin >> N;
	for (ll i = 1; i <= N; i++) cin >> w[i];
	memset(dp, 0, sizeof(dp));
	dp[0] = 1;
	for (ll i = 1; i <= N; i++) {//考虑每个砝码
		//从大到小考虑每个称重j，j>=w[i]
		//如果从小到大，则意味着w[i]可以加很多次
		for (ll j = 100000; j >= w[i]; j--)//此前没有加w[i]，现在考虑加
			//如果此前dp[j - w[i]]为1，则加上w[i]的重量，能达到j，所以dp[j]为1
			dp[j] = max(dp[j], dp[j - w[i]]);
	}
	for (ll i = 1; i <= N; i++) {
		ll siz = 100000 - w[i];
		for (ll j = 1; j <= siz; j++)//此前不放w[i]或放，现在减，相当于放左边和不放
			//如果此前dp[j + w[i]]为1，则减去w[i]的重量，能达到j，所以dp[j]为1
			dp[j] = max(dp[j], dp[j + w[i]]);
	}
	ll ans = 0;
	for (ll i = 1; i <= 100000; i++)
		ans += dp[i];
	cout << ans << endl;
	return 0;
}

大数据201 liyang