[dp+dfs]砝码称重
题目描述
现有 n n n 个砝码，重量分别为 a 1 , a 2 , … , a n a_1, a_2, \ldots,a_n a1,a2,…,an ，在去掉 m m m 个砝码后，问最多能称量出多少不同的重量（不包括 0 0 0 ）。
输入格式
第一行为有两个整数
n
n
n 和
m
m
m ，用空格分隔。
第二行有
n
n
n 个正整数
a
i
a_i
ai ，表示每个砝码的重量。
输出格式
输出一行一个整数，表示最多能称量出的重量的数量。
样例
样例输入1：
3 1
1 2 2
样例输出1：
3
样例解释1
在去掉一个重量为
2
2
2 的砝码后，能称量出
1
,
2
,
3
1, 2, 3
1,2,3 共
3
3
3 种重量。
数据范围
对于
20
%
20\%
20% 的数据，
m
=
0
m = 0
m=0。
对于
50
%
50\%
50% 的数据，
m
≤
1
,
n
≤
10
m \le 1,n\le 10
m≤1,n≤10。
对于
100
%
100\%
100% 的数据，
n
≤
20
,
m
≤
4
,
m
<
n
,
a
i
≤
100
n \le 20, m \le 4,m < n,a_i \le 100
n≤20,m≤4,m<n,ai≤100。
题解
对于
20
%
20\%
20% 的数据，去掉
0
0
0 个砝码，就是一个 01背包 问题。
对于
50
%
50\%
50% 的数据，枚举每个数是否选择，判断去掉个数后做 01背包。
对于 100 % 100\% 100% 的数据，对上面的搜索进行剪枝，如果去掉个数大于 m m m，返回。也可以枚举去掉的砝码，会快一些。
#include<bits/stdc++.h>
using namespace std;
int n, m;
int a[23];
bool f[23];
int dp[2010];
int ans = 0;
void solve(){//01 背包
memset(dp, 0, sizeof(dp));
dp[0] = 1;
int s = 0;//01 背包每次最多更新到多少
for(int i = 1; i <= n; ++ i){
if(f[i]){
continue;
}
s += a[i];
for(int j = s; j >= a[i]; -- j){
if(dp[j - a[i]]){
dp[j] = 1;
}
}
}
//统计个数
int sum = 0;
for(int i = s; i >= 1; -- i){
if(dp[i]){
++ sum;
}
}
ans = max(ans, sum);
}
//搜索
void dfs(int x, int y){
if(y > m){
solve();
return;
}
for(int i = x + 1; i <= n; ++ i){
f[i] = 1;
dfs(i, y + 1);
f[i] = 0;
}
}