砝码称重(2021年蓝桥杯)

【问题描述】

     你有一架天平和N个砝码，这N个砝码的重量依次是w1,w2,……,wn。（1~n为下标）

     请你计算利用N个砝码一共可以称出多少种不同的重量？

   【注意】砝码可以放在天平的两边

【输入格式】

   第一行包含一个整数N。

   第二行包含N个整数w1,w2,……,wn。（1~n为下标）。

【输出格式】

 一个整数，代表答案

【样例输入】

  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%的评测用例, N >= 1 &&N<=15

对于所有评测用例 ，N <= 1&& N <= 100，N个砝码的总重量不超过100000。

【试题解析】

 本题也是一道典型的动态规划题目。

     设状态dp[i][j]表示i个砝码可称出重量j,则状态转移方程为1为dp[i][j]=dp[i-1][j]，该方程表示i-1个砝码所能称出的重量i个砝码也能称出来，状态转移方程2为dp[i][j] = dp[i][abs(j-a[i])]

     该方程表示加入第i个砝码，看是否能称出i-1个砝码未能称出的重量。

     程序首先从第1个砝码开始，当有新的砝码i加入时，一共分成以下三种情况。

    （1）当前重量j刚好等于加入的砝码a[i]

     将当前的dp[i][j]状态设为1.

     （2）当前重量j大于加入的砝码a[i]

      dp[i][j] = dp[i-1][j-a[i]]，该状态表示j是否能由i-1个砝码能称出的重量与a[i]相加而得。

      （3）当前重量j小于加入的砝码a[i]

       dp[i][j] = dp[i-1][a[i]-j]，该状态表示j是否能由a[i]减去i-1个砝码所能称出的重量而得。

      输入样例如下：

dp[i][j]状态矩阵如下

【参考程序如下】

#include <iostream>
long long dp[102][100002] = {0}; 
using namespace std;
int main(int argc, char** argv) {
	int a[102];
	int n;
	int sum = 0;
	cin >> n;
	for(int i = 1; i <= n;i++)
	{
		cin >> a[i];
		sum += a[i];      // i个砝码所能称出的最大重量是sum 
	}
	for(int i = 1; i <= n; i++)
	    for(int j = 1; j <= sum; j++)
	     {
	     	dp[i][j] = dp[i - 1][j];   //继承i-1的性质
			if(!dp[i][j])
			{
			    if(j == a[i])dp[i][j] = 1;
     			else if(j > a[i]) dp[i][j] = dp[i - 1][j - a[i]];
				else dp[i][j] = dp[i - 1] [a[i] - j];
			}
		}
				int count = 0;
				for(int i = 1; i <= sum;i++)
				  if(dp[n][i]) count++;
				  cout << count;
		
				//  reutrn 0; 	 
}
	

【程序运行结果如下】