【洛谷】P2240 【深基12.例1】部分背包问题（详细思路）

#include <iostream>
#include <iomanip>
using namespace std;
int main()
{
	int N, T;
	cin >> N >> T;
	long double gold[100][3] = {0};
	for (int i = 0; i < N; i++)
	{
		cin >> gold[i][0] >> gold[i][1];
		gold[i][2] = gold[i][1] / gold[i][0];
	}
	long double get = 0;
	int totalWeight = 0;
	for (int i = 0; i < N; i++)
		totalWeight += gold[i][0];
	if (totalWeight <= T)
	{
		double totalValue = 0;
		for (int i = 0; i < N; i++)
			totalValue += gold[i][1];
		cout << fixed << setprecision(2) << totalValue << endl;
		return 0;
	}
	while (T > 0)
	{
		int max = 0;
		for (int i = 0; i < N; i++)
		{
			if ((gold[i][2] > gold[max][2] || (gold[i][2] == gold[max][2] && i > max) || gold[max][0] == 0) && gold[i][0] > 0)
				max = i;
		}
		if (T >= gold[max][0])
		{
			T -= gold[max][0];
			get += gold[max][1];
			gold[max][0] = 0;
		}
		else
		{
			get += T * gold[max][2];
			T = 0;
		}
	}
	cout << fixed << setprecision(2) << get << endl;
	return 0;
}

此题两个坑点：精度问题和时间问题

由于涉及到求金币重量价值比，除法存在精度误差，所以直接把精度拉满，涉及到除法的数据类型都设为long double型。

时间问题，第一组测试点要靠以下代码快速判断⬇

    int totalWeight = 0;
	for (int i = 0; i < N; i++)
		totalWeight += gold[i][0];
	if (totalWeight <= T)
	{
		double totalValue = 0;
		for (int i = 0; i < N; i++)
			totalValue += gold[i][1];
		cout << fixed << setprecision(2) << totalValue << endl;
		return 0;
	}

• 思路：在当前的 while 循环中，只要背包剩余重量 T 大于 0 就会持续循环，但实际上，如果所有物品的总重量都已经小于等于 T，意味着可以直接把所有物品放入背包，无需再一次次循环去选择物品了，这样可以提前结束循环，减少不必要的比较和计算操作。

• 通过先计算所有物品的总重量并与背包容量 T 进行比较，在合适的情况下提前结束程序，避免了多余的循环，在某些输入数据场景下（比如背包容量很大，物品总重量相对较小时）可以显著减少程序运行时间，虽然没有改变整体的时间复杂度量级，但可以在一定程度上优化实际运行效率。

 这样就可以跳出TEL的坑啦