洛谷P5194 Scales S

url: https://www.luogu.com.cn/problem/P5194

tag:
USACO05DEC，dfs，剪枝，搜索

思路：
先按照从大到小排序，然后计算前缀和。之后每次dfs，先判断上一个累加的结果有没有超过w，如果有就return，否则就更新res，然后判断是不是所有点都判断完了，如果是，则return。之后计算一下剩余的值之和，如果剩余的值之和加上当前累加的值比res小就直接return。否则就判断下一个值加上累加的值会不会超过w如果没有加加上那个值，然后递归dfs，最后再dfs没有加上这个值的情况。

代码：

#include <iostream>
#include <algorithm>
using namespace std;
long long n, w;
long long d[1010], sum[1010];
long long res = -1;
bool st[1010];
void dfs(int u, long long tmp)
{
    if (tmp > w) return;
    res = max(res, tmp);
    if (u == n) return;
    long long remain = sum[n] - sum[u];
    if (remain + tmp <= res) return;
    if (tmp + d[u + 1] <= w) dfs(u + 1, tmp + d[u + 1]);
    dfs(u + 1, tmp);

}
bool cmp (long long &a, long long &b)
{
    return a > b;
}
int main()
{
    cin >> n >> w;
    for (int i = 1; i <= n; i ++)
    {
        cin >> d[i];
    }
    sort(d + 1, d + 1 + n, cmp);
    for (int i = 1; i <= n; i ++) sum[i] = sum[i - 1] + d[i];
    dfs(0, 0);
    cout << res;
    return 0;
}