dfs
C++ 代码
#include<iostream>
using namespace std;
const int N = 110, M = 200010;
int n,w[N];
bool st[M];
int cnt;
void dfs(int u,int sum){
if(u == n + 1){
if(sum > 0 && !st[sum]){ //sum > 0 是因为左右边是对称的关系所以-sum和sum本质是一样的,不能重复计入
st[sum] = true; //全部选完再进行标记
cnt ++;
}
return ;
}
dfs(u + 1,sum + w[u]); //顺序无所谓
dfs(u + 1,sum - w[u]);
dfs(u + 1,sum);
}
int main(){
cin >> n;
for(int i = 1; i <= n; i ++) cin >> w[i];
dfs(1,0); 从第一个砝码开始dfs,此时sum = 0
cout << cnt << endl;
return 0;
}
dp
y式dp
状态转移方程
f[i][j] = f[i][i - 1] + f[i - 1][j - w[i]] + f[i - 1][j + w[i]]
C++ 代码
#include<iostream>
#include<cmath>
using namespace std;
const int N = 110, M = 200010;
int f[N][M]; // 表示从前i个砝码选 总重量为j的集合
int n,w[N];
int sum; //表示砝码可以称出的最大重量
int main(){
cin >> n;
for(int i = 1; i <= n; i ++){
cin >> w[i];
sum += w[i];
}
f[0][0] = true; // 初始化从前0个选重量为0 该方式存在
for(int i = 1; i <= n; i ++){
for(int j = 0; j <= sum; j ++){
f[i][j] = f[i - 1][j] + f[i - 1][abs(j - w[i])] + f[i - 1][j + w[i]];
// f[i - 1][j]表示不选的方案数 ,f[i - 1][j + w[i]]表示选择+w[i]的方案数,f[i - 1][j - w[i]]表示选择-w[i]的方案数
//-sum和sum本质是一样的 故使用绝对值
}
}
for(int j = 1; j <= sum; j ++){
if(f[n][j]) ans ++; //如果方案数不为0 说明可以凑出重量为j 所以ans++
}
cout << ans;
return 0;
}
作者代码写这么好是不是经常易大山啊
卡莎,你的dfs过不了啊
相信卡神
dfs蓝桥杯暴力骗分的 ,可以过50%的数据
### 感谢分享,老哥dp忘了定义ans了。
为什么第二种方法的M = 200010?不是以及状态表示方程里面已经使用abs了吗?
当j 等于sum时,j + w[i] 可能就会超过100000,从而导致f[i - 1][j + w[i]]计算时出现问题无法正确转移过来,所以M就要开成j + w[i]的最大值200000
为啥会出现错误转移的问题, 我也因为这个过不去