文章目录

• 前言
• 一、题目描述
• • 输入格式
  • 输出格式
  • 样例输入
  • 样例输出
  • 样例说明
  • 评测用例规模与约定
  • • 运行限制
• 二、思路
• 三、完整代码

前言

蓝桥杯2021年省赛，编程题（C++）

这道题主要考察了基础的动态规划思想

一、题目描述

你有一架天平和 N 个砝码，这 N 个砝码重量依次是 W1, W2,⋅⋅⋅, WN。

请你计算一共可以称出多少种不同的重量？ 注意砝码可以放在天平两边。

输入格式

输入的第一行包含一个整数 N。

第二行包含 N 个整数：W1,W2,W3,⋅⋅⋅,WN。

输出格式

输出一个整数代表答案。

样例输入

3
1 4 6

样例输出

10

样例说明

能称出的 10 种重量是：1、2、3、4、5、6、7、9、10、11。

1=1；

2 = 6 − 4 (天平一边放 6，另一边放 4)；

3=4−1；

4=4；

5=6−1；

6=6；

7=1+6；

9=4+6−1；

10=4+6；

11=1+4+6。

评测用例规模与约定

对于 50%的评测用例，1≤N≤15。

对于所有评测用例，1≤N≤100,N个砝码总重不超过 100000。

运行限制

• 最大运行时间：1s
• 最大运行内存: 256M

二、思路

我们对于拿过来的每一种砝码，有两种选择，一种是放，另一种是不放。放的话，其实又有两种选择，一种是放到左边，一种是放到右边，但是注意，放到左边和右边的情况是不一样的。试想，现在天平上左边有1kg , 5kg两个重量的砝码，而天平的右边现在没有砝码，那么我取来一个重7kg的砝码，先选择放到左边，现在重量是1+5+7=13，而假如我放到右边呢，其实最终可以称出来的重量是abs（1+5-7）即1，因此这也引出了解决本题的dp思路。

我们建立dp[i][j]的过程及含义如下：

dp[i][j]表示在当前 i 种砝码下，对于重量 j 来说，是否能够拼凑出来，即dp的值只有0和1两种，1表示能够拼凑出来，0表示不能够拼凑出来。那么对于第 i 个砝码来说，重量为w[i]，那么对于某一重量 j ，如果dp[i-1][j]==1，即在前面的砝码已经被遍历的情况下，可以拼凑出 j 这个重量，那么我们有：

dp[i][j]=dp[i-1][j] //这种情况是当前这个砝码选择不放

dp[i][j+w[i]]=1; //这种情况是当前这个砝码放到左边，比如（左：15，右5；实际上可以等于做10，右0）

dp[i][abs(j-w[i])]; //这种情况是当前这个砝码放到右边

思路大致是这样的，下面来看具体代码

三、完整代码

#include<bits/stdc++.h>
using namespace std;
int dp[105][100005];
int w[150];
int main()
{
	int n;
	cin>>n;
	int sum=0;
	for(int i=0;i<n;i++)
	{
		cin>>w[i];
		sum+=w[i];
	}
	sort(w,w+n);  //将砝码从小到大排列
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<=sum;j++)
		{
			dp[i][j]=0;
		}
	}
	dp[0][w[0]]=1;  //第一个砝码先赋初值
	for(int i=1;i<n;i++)  //遍历砝码的次序
	{
		dp[i][w[i]]=1;   //当前重量一定可以称出，即只放这一个砝码
		for(int j=1;j<=sum;j++)  //对于每一种重量，分别判断
		{
			if(dp[i-1][j]==1)  //之前能凑出来这种重量
			{
				dp[i][j]=1;
				dp[i][abs(j-w[i])]=1;
				dp[i][j+w[i]]=1;
			}
		}
	}
	int ans=0;
	for(int i=1;i<=sum;i++)
	{
		if(dp[n-1][i]==1)
		{
			ans++;
		}
	}
	cout<<ans<<endl;
	return 0;
}