Data Structures Algorithms 简明教程
Fractional Knapsack Problem
背包问题表述如下：给定一项集合，其包含重量和利润值，必须确定要添加到背包中的项目子集，以便项目的总重量不得超过背包的限制，其总利润值最大。
它是使用贪婪算法解决的最流行问题之一。它被称为 Fractional Knapsack Problem 。
为了更简单地解释这个问题，考虑一个有 12 个问题且每个问题 10 分的考试，其中只能尝试 10 个问题才能获得 100 分的高分。现在，考试的参加者必须计算最有利的问题 - 即他们有信心的问题 - 以获得最高分。但是，他不能尝试全部 12 个问题，因为对于尝试回答这些问题不会获得任何额外分数。这是背包问题的最基本的实际应用。
Knapsack Algorithm
作为输入，分数背包算法将要添加到背包中的物品的重量 (Wi) 和利润值 (Pi) 作为输入，而输出是添加到背包中的物品的子集，该子集不会超过限制并且具有最大利润。
Algorithm
-
考虑所有物品及其各自提到的重量和利润。
-
计算所有物品的 Pi/Wi，并根据其 Pi/Wi 值对其进行降序排列。
-
在不超过限制的情况下，将物品添加到背包中。
-
如果背包仍然可以存放一些重量，但其他物品的重量超过了限制，则可以添加下一个时间的几分之一部分。
-
因此，给它起了分数背包问题这个名字。
Solution
Step 1
给定，n = 5
Wi = {3, 3, 2, 5, 1}
Pi = {10, 15, 10, 12, 8}计算所有项目的 Pi/Wi
Step 2
根据 Pi/Wi 对所有项目进行降序排列
Step 3
在不超过背包容量的情况下，将物品放入背包中以获得最大利润。
Knapsack = {5, 2, 3}但是，背包仍然可以容纳 4 公斤的重量，但是下一个重量为 5 公斤的物品将超过容量。因此，将在背包中仅添加 5 公斤的 4 公斤重量。
因此，背包的重量 = [(1 * 1) + (1 * 3) + (1 * 2) + (4/5 * 5)] = 10，最大利润 = [(1 * 8) + (1 * 15) + ( 1 * 10) + (4/5 * 20)] = 37。