蓝桥杯（砝码称重，C++）

称重，C++）"/>

蓝桥杯（砝码称重，C++）

 思路：

1、用到动态规划思想。

2、用ans[i][j]记录用前i个砝码，能不能称出重量j。

3、详细思路见代码注释，易懂。

#include<iostream>
#include<cmath>
using namespace std;
int main()
{int n;int a[110];//记录每个砝码重量int sum = 0;//计算所有砝码总重量int ans[110][100005];//abs[i][j]记录用前i个砝码，能不能称出重量jcin >> n;for (int i = 1; i <= n; i++){cin >> a[i];sum += a[i];}for(int i=1;i<=n;i++)//遍历所有砝码for (int j = 1; j <= sum; j++){ans[i][j] = ans[i - 1][j];//先继承前i-1个砝码，能不能称出重量jif (ans[i][j] == 0)//不能称出，则加入第i个砝码，判断能不能称出重量j{if (j == a[i]) ans[i][j] = 1;//说明只用第i个就可以称出重量jif (ans[i - 1][j + a[i]] == 1) ans[i][j] = 1;//判断第i-1个砝码能不能称出j+a[i]的重量，可以则只要减去第i个砝码质量if (ans[i - 1][abs(j - a[i])] == 1) ans[i][j] = 1;//判断第i-1个砝码能不能称出j-a[i]的重量，可以则加上的i个砝码重量}}int ad = 0;for (int i = 1; i <= sum; i++)if (ans[n][i] == 1) ad++;cout << ad;
}