砝码称重(动态规划c++实现)

本文主要是介绍砝码称重(动态规划c++实现)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

---

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

请你计算一共可以称出多少种不同的正整数重量？

注意砝码可以放在天平两边。

---

输入

---

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

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

---

输出

---

输出一个整数代表答案。

---

样例

输入样例：
3
1 4 6
输出样例：
10

代码

#include<iostream>
#include<cmath>
using namespace std;
const int N = 110,M=2e5+10,B = M/2;
int n;
int q[N];
bool f[N][M];
bool st[M];int main(){scanf("%d",&n);int sum = 0;for(int i=1;i<=n;i++) {scanf("%d",&q[i]);sum+=q[i];}f[0][B] = true;int res = 0;for(int i=1;i<=n;i++){for(int j=-sum;j<=sum;j++){f[i][j+B] |= f[i-1][j+B];if(j-q[i]>=-sum) f[i][j+B] |= f[i-1][j-q[i]+B];if(j+q[i]<=sum) f[i][j+B] |= f[i-1][j+q[i]+B];}}for(int i=1;i<=sum;i++) if(f[n][i+B]) res++;printf("%d",res);
}

这篇关于砝码称重(动态规划c++实现)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---