问题:
你有一架天平和 N个砝码,这 N个砝码重量依次是 W1,W2,⋅⋅⋅,WN。
请你计算一共可以称出多少种不同的正整数重量?
注意砝码可以放在天平两边。
- dfs //超时的 只能骗分
//砝码称重 dfs
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+7;
bool vis[N];//使用一个布尔数组下标来表示访问过的体重
int w[N],n;
void dfs(int cur,int weight){
vis[abs(weight)]=true;//标记访问过
if(cur>n) return;//递归结束
dfs(cur+1,weight+w[cur]); //天平右侧
dfs(cur+1,weight-w[cur]); //天平左侧
dfs(cur+1,weight); //不加
return;
}
int main(){
scanf("%d", &n);
int sum=0;
for(int i=1;i<=n;i++){
scanf("%d",&w[i]);
sum+=w[i]; //所有天平重量的总重,枚举的范围
}
dfs(1,0);
int ans=0;
for(int i=1;i<=sum;i++)
if(vis[i]) ans++; //标记过的重量+1 就是所有能称出的体重
printf("%d",ans);
return 0;
}
2.DP
解题思路:
要求能够称出来的重量,那么我们将重量从1到所有的砝码重量全部加起来枚举,
从中满足条件的重量就是能够称出来的,那么可以转化为 一个有限制的选择问题(背包问题)
f[i][j]状态表示就是:只从前i个物品中选且称出的重量为j的方案的 集合
那么前一个状态可以分为三类:
1.不称 f[i-1][j]
2.放在天平右端 f[i-1][j+w]
3.放在天平左端 f[i-1][abs(j-w)] //数组下标不能为负,直接用绝对值表示重量
因为状态表示是能够称出重量的方案,所以状态计算为是否非空,三类只要满足条件就可以,用或运算
#include <iostream>
using namespace std;
const int N=110,M=2e5+10;
int n;
int w[M];
bool f[N][M];
//f[i][j]状态表示:取i个砝码称出j重量的方案数
int main(){
cin>>n;
int sum=0;
for(int i=1;i<=n;i++){
cin>>w[i];
sum+=w[i];
}
f[0][0]=true;
for(int i=1;i<=n;i++)
for(int j=0;j<=sum;j++)
f[i][j]=f[i-1][j+w[i]]||f[i-1][abs(j-w[i])]||f[i-1][j];
//只要有一个非空,f[i][j]就非空
int ans=0;
for(int j=1;j<=sum;j++)
if(f[n][j]) ans++; //不为零说明可以选出这个质量的砝码
cout<<ans<<endl;
return 0;
}