本文主要是介绍蓝桥杯B组 --- 砝码称重，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
你有一架天平和 N 个砝码，这 N 个砝码重量依次是 W1,W2,⋅⋅⋅,WN
请你计算一共可以称出多少种不同的正整数重量？
注意砝码可以放在天平两边。
输入格式
输入的第一行包含一个整数 N。
第二行包含 N 个整数：W1,W2,W3,⋅⋅⋅,WN
输出格式
输出一个整数代表答案。
数据范围
对于 50%50% 的评测用例，1≤N≤15。
对于所有评测用例，1≤N≤100，N 个砝码总重不超过 105。输入样例：
3 1 4 6输出样例：
10样例解释
能称出的 1010 种重量是：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。
这道题首先可以暴力dfs枚举两个方向，要么加这个数要么减去这个数，显而易见这里肯定会超时，这里有哪位大佬会如何剪枝的可以在评论区留言一下，感谢。
#include <iostream>
using namespace std;
const int N = 20;
int a[N];
int n;
bool st[100010];
bool count[40];
int num_sum = 0;
void dfs(int start ,int sum)
{if(sum > 0){st[sum] = true;//只要找到sum>0的情况就让其当前状态变为true}for(int i = start;i <= n;i++)//组合型枚举模板{if(!count[i]){count[i] = true;//+a[i]sum += a[i];dfs(i + 1 , sum);sum -= a[i];//注意还原现场//-a[i]sum -= a[i];dfs(i + 1 , sum);sum += a[i];count[i] = false;}}
}
int main()
{cin >> n;for(int i = 1;i <= n;i++){cin >> a[i];num_sum += a[i];}dfs(1,0);int ans = 0;for(int i = 1;i <= num_sum;i++){if(st[i] == true)//累加被计算出的值ans++;}cout << ans << endl;return 0;
}最后当然只可以通过50%hhh。
第二种方法肯定就是动态规划，还是在此基础上分成两个区间，选与不选当前a[i]数，然后在选择的时候分成两种方向，一种+a[i]一种-a[i]。
那么其状态转移方程：
dp[i][j] = dp[i - 1][j] + dp[i - 1][j + a[i]] + dp[i - 1][abs(j - a[i])];随后因为只能选一次，所以按照01背包的模板就可以写成：
#include <iostream>
using namespace std;
const int N = 120;
int dp[N][100100];
int a[N];
int main()
{int n;cin >> n;int sum = 0;for(int i = 1;i <= n;i++){cin >> a[i];sum += a[i];} dp[0][0] = 1;for(int i = 1;i <= n;i++){for(int j = 0;j <= sum;j++){dp[i][j] = dp[i - 1][j] + dp[i - 1][abs(j - a[i])] + dp[i - 1][j + a[i]];}}int ans = 0;for(int i = 1;i <= sum;i++){if(dp[n][i])ans++;//这里的ans跟上面那个dfs的作用一样}cout << ans << endl;return 0;
}这篇关于蓝桥杯B组 --- 砝码称重的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
