P5194 [USACO05DEC] Scales S

看到题目很容易想到递归，每件物品选或不选即可，时间复杂度,可以过

#include<iostream>
#include<vector>

void dfs(int& res, int& curr, std::vector<int>& v, int index,int& C)
{
	if (curr > C)//超重直接返回
		return;
	res = std::max(res, curr);
	if (index == v.size())//选完了
		return;
	curr += v[index];
	dfs(res, curr, v, index + 1, C);//选
	curr -= v[index];
	dfs(res, curr, v, index + 1, C);//不选
}

int main()
{
	int N, C;
	std::cin >> N >> C;
	std::vector<int> v(N);
	for (int i = 0; i < N; i++)
	{
		std::cin >> v[i];
	}
	int res = 0, curr = 0;
	dfs(res, curr, v, 0, C);
	std::cout << res;
}

由于剩下4个点超时，而输入的序列又有序，自然就可以想到剪枝，我们可以直接从后往前找，如果当前的所有砝码和当前的重量比res小，那后面的路线一定无法找到更好的结果，因为当前情况已经是把当前所有剩下的砝码全选。同样，如果当前砝码加上当前可选砝码总重量curr大于C，那么当前砝码不可选。最后，如果当前剩下的砝码总重量加上当前可选重量小于res，直接剪掉。

#include<iostream>
#include<vector>

void dfs(int& res, int& curr, std::vector<int>& v, std::vector<long long>& sum,int index, int& C)
{
	if (index == 0)
	{
		res = std::max(res, curr);
		return;
	}
	if (curr > C)
		return;
	if (curr + sum[index] < C)//由于是非降序列，已经是此路线能达到的最优重量，剪掉剩余路线
	{
		res = std::max(res, curr + (int)sum[index]);
		return;
	}
	if (v[index] + curr > C)//此砝码超重不可选，剪掉剩余路线
	{
		dfs(res, curr, v, sum, index - 1, C);
		return;
	}
	if (sum[index] + curr <= res)//剩下砝码加起来都没有当前答案重，不可能存在更优的结果，剪掉剩余路线
		return;
	dfs(res, curr, v, sum, index - 1, C);
	curr += v[index];
	dfs(res, curr, v, sum, index - 1, C);
	curr -= v[index];
}

int main()
{
	int N, C;
	std::cin >> N >> C;
	std::vector<int> v(N+1);
	std::vector<long long> sum(N + 1);
	for (int i = 1; i <= N; i++)
	{
		std::cin >> v[i];
		sum[i] = sum[i - 1] + v[i];
	}
	int res = 0, curr = 0;
	dfs(res, curr, v, sum, N, C);
	std::cout << res;
}