[数据结构与算法]搜索剪枝。Scales S详解

传送门，

题目大意：

有一串不递减序列的序列砝码（从第三个开始，每个砝码质量最少是前两个砝码的和），要求用天平秤重，给出天平的最大承重量，砝码数量和砝码的重量，求最大的称量数。

思路：求最大称量数就相当于求多少个数拼成一个最大的数，那就可以用到从大到小的挑选（优化一），如果大的这个可以。前面一定有砝码可以凑成这个大的数，而我们直接选这个大的数的话，就不用再搜索了，然后对于从后往前面选的话，可以再进行一次优化，如果已经选择的砝码的质量加上再选择第i个砝码加上之前所有的砝码的质量小于最大承重量的时候，我们就可以一次性选择i包括i之前全部的砝码质量，这里就用到了前缀和。然后更新最大值，return即可。然后对于这个问题也可以简化为选货物，我只能选或者不选，搜索的方向就很明确了，上代码。快读，没想到吧，哈哈哈。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define std std::ios::sync_with_stdio(0)
#define mem(a,b) memset(a,b,sizeof(a));
const int maxn =1e3+10;
ll w[maxn],sum[maxn];
int C,n;
ll ans=0;
inline void read(ll& x)
{
	int f = 1; x = 0; char s = getchar();
	while (s < '0' || s>'9')
	{
		if (s == '-')
			f = -1;
		s = getchar();
	}
	while (s >= '0' && s <= '9')
	{
		x = x * 10 + s - '0';
		s = getchar();
	}
	x*= f;
}
void dfs(ll nn,int xx)                  //经典取货问题，每次都只有取货或者不取或两种情况
{
	if (xx == 0)              //如果没有石头了就直接返回
		return;
	
	if (nn > C)
		return;
	ans = ans > nn ? ans : nn;        //放在上一个的if后面，不然会得到一个比C大的值

	if (nn + sum[xx] <= C)          //如果前面的都拿到之后也比最大值的值小，就直接都拿了，就相当于遍历了之前的所有情况
	{
		ans = ans > (nn + sum[xx]) ? ans : (nn + sum[xx]);
		return;
	}
	if (nn + w[xx] <= C)
		dfs(nn + w[xx], xx-1);
	dfs(nn, xx - 1);
}

int main()
{

	scanf("%d %d", &n, &C);
	for (int i = 1; i <=n; i++)
	{
		read(w[i]);
		sum[i] = sum[i - 1] + w[i];
	}
	dfs(0,n);
	printf("%lld\n", ans);
	return 0;
}