使用 C++ 的分数背包

在本文中，我们将学习使用 C++ 解决分数背包问题。我们将从查看问题陈述开始，然后转向解决方案。该问题是许多流行的经典问题之一。它与它的兄弟 0-1 背包有很大不同0-N背包。这是一种贪心算法，另外两种是动态规划算法。

什么是分数背包？

您将获得某些物品的重量和价格清单以及一定容量（例如 W）的袋子/背包。您的任务是以这样的方式填充这个袋子，使您在这个袋子中携带的所有物品的总价格最大对于所有配置。您可以收集任何对象的整体或部分。

分数背包算法

好吧，我们来看看解决这个问题的算法。由于我们将对此问题实现贪婪解决方案，因此下面是贪婪算法的简要描述。

什么是贪心算法？

在这些算法中，我们的目标是在每一步实现局部最大值/最小值，以便最终实现全局最大值/最小值。也就是说，我们最大化/最小化每个子问题的答案，从而得出整个问题的最大/最小答案。

Note:你将要做出的贪婪的选择一定是一个安全的举动。

Safe Move:如果该初始移动存在可靠的最佳答案，则该移动称为安全移动。

使用贪婪算法的策略

以下是开发完美贪心算法时应遵循的步骤。

• 做出贪心的选择
• Prove它是一个安全移动这样你就不会编写代码并最终发现这不是一个可行的选择。这个特定的步骤是贪心算法最重要的步骤。
• 减少到更小的问题
• 解决所有较小的问题。

伪代码

现在我们将逐步介绍背包算法。

• 按价值/重量比的降序对物品进行排序。仅此一步就降低了从其中选择最佳项目的时间复杂度O(N) to O(log2N).
• 现在我们开始通过运行来选择对象for 循环从 i = 0 到 i = N
• Lemma: There exists an optimal solution that uses as much as possible of an item with the maximum value per unit of weight.
  • 证明：尝试用不同的选择标准填充背包，你得到的总价值总是小于最大可能值。

下面所附的例子证明我们的引理是正确的。

• 现在，如果价值/重量比最大的物品的尺寸适合背包，则将其全部取出。否则，取其中最大可能的分数。
• Reduce the capacity of the bag by the weight of the item taken.
  • 如果整个项目都被拿走，那么：capacity = capacity - weight[this_item].
  • 否则，由于背包已满，容量变为0。
• Add the value of the fraction of this item taken to the total value.
  • 如果整个项目被拿走：total_value += value[this_item]
  • 否则，value += fraction_of_weight_taken * value[this_item].
• 如果容量变为0，则跳出循环。

伪代码的整体结构变为：

演示分数背包的 C++ 程序

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

// this custom comparator function will allow
// us to compare our vector based on the
// ratio of values to weights
bool compare(pair <float, int> p1, pair <float, int> p2)
{
	return p1.first > p2.first;
}

int fractional_knapsack(vector <int> weights, vector <int> values, int capacity)
{
	int len = weights.size();
	int total_value = 0;

	// vector to store the items based on their value/weight ratios
	vector <pair <float, int>> ratio(len, make_pair(0.0, 0));

	for(int i = 0; i < len; i++)
		ratio[i] = make_pair(values[i]/weights[i], i);

	// now sort the ratios in non-increasing order
	// for this purpose, we will use our custom
	// comparator function
	sort(ratio.begin(), ratio.end(), compare);

	// start selecting the items
	for(int i = 0; i < len; i++)
	{
		if(capacity == 0)
			break;

		int index = ratio[i].second;

		if(weights[index] <= capacity)
		{
			// we item can fit into the knapsack
			// hence take the whole of it
			capacity -= weights[index];

			// add the value of this item to the
			// final answer
			total_value += values[index];
		}
		else
		{
			// this item doesn't fit into the bag
			// and thus we take a fraction of it
			int value_to_consider = values[index] * (float(capacity)/float(weights[index]));
			total_value += value_to_consider;
			capacity = 0;
		}
	}

	return total_value;
}

int main()
{
	cout << "Enter the weights of the items, press -1 to stop" << endl;

	vector <int> weights;

	while(true)
	{
		int weight;
		cin >> weight;

		if(weight == -1)
			break;

		weights.push_back(weight);
	}

	cout << "Enter the values of each item, press -1 to stop" << endl;
	
	vector <int> values;

	while(true)
	{
		int value;
		cin >> value;

		if(value == -1)
			break;

		values.push_back(value);
	}

	cout << "Enter the capacity of the knapsack" << endl;

	int capacity;
	cin >> capacity;

	cout << "The maximum value possible based on current list is: " << fractional_knapsack(weights, values, capacity) << endl;
}

Output

结论

分数背包是一种贪婪算法，在本文中，我们研究了它的实现。我们简要了解了贪婪算法，然后讨论了分数背包算法的伪代码。我们证明了我们的贪婪选择是安全的，最后，我们编写了一个 C++ 程序来演示这个解决方案。这个概念的总体时间复杂度是：O(Nlog2N)。今天的内容就到这里，感谢您的阅读。

进一步阅读

如果你想了解更多关于背包和其他贪心算法的知识，可以参考以下网站。

https://brilliant.org/wiki/greedy-algorithm

https://en.wikipedia.org/wiki/Knapsack_problem