砝码称重
你有一架天平和 N 个砝码,这 N 个砝码重量依次是 W1,W2,⋅⋅⋅,WN。
请你计算一共可以称出多少种不同的正整数重量?
注意砝码可以放在天平两边。
算法
(暴搜)
- 按物品搜索
- 放左边、放右边、不放
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1E5+10;
int n; //砝码个数
int a[N]; //记录每个砝码重量
bool st[N]; //判断
void dfs(int u,int w){ //前u个砝码称重后总重量为w
if(u==n){
if(w<=0) return;
st[w] = true;
return;
}
dfs(u+1,w); //不放
dfs(u+1,w+a[u]); //放左边
dfs(u+1,w-a[u]); //放右边
}
int main(){
cin>>n;
int sum = 0; //总质量
for(int i=0;i<n;i++){
cin>>a[i];
sum+=a[i];
}
dfs(0,0);
int ans = 0; //方案个数
for(int i = 0;i<=sum;i++){
if(st[i]) ans++;
}
cout<<ans<<endl;
return 0;
}