使用C++实现小数背包问题

在这篇文章中，我们将学习如何使用C++解决分数背包问题。我们将首先看一下问题陈述，然后再转向解决方案。这个问题是众多经典问题中的一个。它与其兄弟问题0-1背包和0-N背包相当不同。这是一种贪婪算法，而其他两种是动态规划算法。

什么是分数背包问题？

你被给予某些物品的重量和价格清单，以及一个特定容量的袋子/背包，称为W。你的任务是以这样的方式填满这个袋子，使得你放入袋子的所有物品的总价格对于所有配置来说都是最大的。而且你可以整个地或者部分地收集任何物品。

分数背包算法

好的，让我们来看一下解决这个问题的算法。由于我们将实施一种贪婪算法来解决这个问题，下面是贪婪算法的简要描述。

什么是贪婪算法？

在这些算法中，我们的目标是在每一步中实现局部最大/最小值，以便最终达到全局最大/最小值。也就是说，我们在解决每个子问题时都要最大化/最小化答案，这将带领我们找到整体问题的最大/最小答案。

注意：你即将做出的贪婪选择必须是一个安全的行动。 (Zhù yì: Nǐ jí zuò chū de shì de .)

安全着法：若存在与初始着法相应的可靠的最优解，该着法即为安全着法。

与贪婪算法合作的策略

以下是你应该遵循的步骤，以开发完美的贪婪算法。

• Make a greedy choice
• Prove that it is a safe move so that you don’t write the code and find out in the end that it was not a feasible choice. This particular step is the most important step of greedy algorithms.
• Reduce to a smaller problem
• Solve all the smaller problems.

伪代码

现在我们将逐步学习背包算法。

• Sort the items in decreasing order of value/weight ratio. This step alone decreases the time complexity of selection of the best item from O(N) to O(log2N).
• Now we start selecting the objects by running a for loop from i = 0 to 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.

  Proof: Try filling the knapsack by a different selection criteria, you will always get smaller total value than the maximum possible value.

以下附件的例子证明了我们的引理是正确的。

• Now if the size of the item with maximum value/weight ratio fits the knapsack, take the whole of it. Otherwise, take the maximum possible fraction of it.
• Reduce the capacity of the bag by the weight of the item taken.

  If the whole item is taken then: capacity = capacity – weight[this_item].
  Otherwise, the capacity becomes 0 because the knapsack becomes full.

• Add the value of the fraction of this item taken to the total value.

  If the whole item is taken: total_value += value[this_item]
  Otherwise, the value += fraction_of_weight_taken * value[this_item].

• If capacity becomes 0, break out of the loop.

伪代码的总体结构变为：

展示分数背包问题的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;
}

产出

结论

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

进一步阅读

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

贪婪算法是一种常用于解决优化问题的算法。它通过在每个步骤中都选择当下最优的选择，最终达到全局最优解。

以下是对《0/1背包问题》维基百科页面的中文释义：

0/1背包问题，又称为背包问题，是一个组合优化问题，旨在从给定的可选项（物品）中选择特定数量的物品来装入容量限制的背包，以使物品的总价值最大化，同时保持不超出背包的容量限制。