P5194 [USACO05DEC]Scales S(这个剪枝还没看懂

#include <iostream>
#include <algorithm>
//所以说题目中的第三个砝码以及之后的砝码必是前面两个砝码之和之大为前置条件
//没必要自己弄
using namespace std;
const int M = 1e3 + 1;
long long sum[M], a[M], ans, n, c;
void dfs(int cur, long long x)//cur表示当前为第几个砝码，x表示目前重量
{
    if (x > c)return;//如果大了 直接跳出
    if (sum[cur - 1] + x <= c)
        //主要是这里优化了很多
    {    //如果前面那些砝码可以全部取走，那直接取走即可。
        ans = max(ans, sum[cur - 1] + x);
        return;
    }
    ans = max(ans, x);
    for (int i = 1; i < cur; i++)
        dfs(i, x + a[i]);//基础暴搜
    return;
}
int main()
{
    cin >> n >> c;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];
        //这里算是一个优化，就是把前面的总和开成一个数组
    }
    dfs(n + 1, 0);//因为是找最大的那个小于c的砝码重量，
    //所以可以采用倒叙查找，会更快
    cout << ans << endl;
    return 0;
}