[dp+dfs]砝码称重

题目描述

现有 $n$ 个砝码，重量分别为 $a_1,a_2,\dots ,a_n$ ，在去掉 $m$ 个砝码后，问最多能称量出多少不同的重量（不包括 $0$ ）。

输入格式

第一行为有两个整数 $n$ 和 $m$ ，用空格分隔。
第二行有 $n$ 个正整数 $a_i$ ，表示每个砝码的重量。

输出格式

输出一行一个整数，表示最多能称量出的重量的数量。

样例

样例输入1：

3 1
1 2 2

样例输出1：

3

样例解释1
在去掉一个重量为 $2$ 的砝码后，能称量出 $1,2,3$ 共 $3$ 种重量。

数据范围

对于 $20\%$ 的数据，$m=0$。
对于 $50\%$ 的数据，$m\le 1,n\le 10$。
对于 $100\%$ 的数据，$n\le 20,m\le 4,m<n,a_i\le 100$。

题解

对于 $20\%$ 的数据，去掉 $0$ 个砝码，就是一个 01背包 问题。

对于 $50\%$ 的数据，枚举每个数是否选择，判断去掉个数后做 01背包。

对于 $100\%$ 的数据，对上面的搜索进行剪枝，如果去掉个数大于 $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;
	}
}