洛谷P1411 砝码称重

传送门啦

这个题总体思路就是先搜索在 $ dp $

void dfs(int keep,int now){

	//使用  放弃

	if(now > m) return;

	//已经放弃超过m个了，就退出

	if(keep == n){

		if(now == m)  dp();

		return ;

	}

	///如果搜索完后正好符合条件，执行一次dp过程

	dfs(keep + 1 , now);

	//这个砝码选

	vis[keep] = true;//打标记

	dfs(keep + 1 , now + 1);

	//这个砝码放弃

	vis[keep] = false;//取消标记

}

观察题目可得，这个过程可以通过01背包实现。

定义 $ f[i][j] $ 为当前选取到了第j个砝码，如果通过之前的砝码可以称量出重量 $ i $ 那么 $ f[i][j] $ 的值为 $ true $ 。

状态转移方程为： $ f[i][j]=f[i-a[i]][j-1] $

初始状态为 $ f[0][j]=true $

最后 $ f[i][n] $ 中 $ true $ 的个数就是通过这些砝码可以计算出的重量值。通过一维数组，我们可以只定义一个 $ f[i] $ 数组，降低了时间复杂度，注意此时内层循环倒序。

#include <iostream>

#include <cstring>

#include <cstdio>

#include <algorithm>

using namespace std;

inline int read(){

	char ch = getchar();

	int f = 1 , x = 0;

	while(ch > '9' || ch < '0'){if(ch == '-')f = -1;ch = getchar();}

	while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + ch - '0';ch = getchar();}

	return x * f;

}

int n,m,a[300];

bool vis[300];

int ans,f[3000],tot,res;

void dp(){

	memset(f , 0 , sizeof(f));

	f[0] = true;  ans = tot = 0;

	for(int i=0;i<n;i++){

		if(vis[i])  continue;

		for(int j=tot;j>=0;j--)

			if(f[j] && !f[j+a[i]]){

				f[j+a[i]] = true;

				ans++;

			}

		tot += a[i];

	}

	res = max(ans , res);

}

void dfs(int keep,int now){

	//使用  放弃

	if(now > m) return;

	if(keep == n){

		if(now == m)  dp();

		return ;

	}

	dfs(keep + 1 , now);

	vis[keep] = true;

	dfs(keep + 1 , now + 1);

	vis[keep] = false;

}

int main(){

	n = read(); m = read();

	for(int i=0;i<n;i++) {

		a[i] = read();

	}

	dfs(0 , 0);

	printf("%d\n",res);

	return 0;

}