Data Structures Algorithms 简明教程

Fractional Knapsack Problem

背包问题表述如下：给定一项集合，其包含重量和利润值，必须确定要添加到背包中的项目子集，以便项目的总重量不得超过背包的限制，其总利润值最大。

The knapsack problem states that − given a set of items, holding weights and profit values, one must determine the subset of the items to be added in a knapsack such that, the total weight of the items must not exceed the limit of the knapsack and its total profit value is maximum.

它是使用贪婪算法解决的最流行问题之一。它被称为 Fractional Knapsack Problem 。

It is one of the most popular problems that take greedy approach to be solved. It is called as the Fractional Knapsack Problem.

为了更简单地解释这个问题，考虑一个有 12 个问题且每个问题 10 分的考试，其中只能尝试 10 个问题才能获得 100 分的高分。现在，考试的参加者必须计算最有利的问题 - 即他们有信心的问题 - 以获得最高分。但是，他不能尝试全部 12 个问题，因为对于尝试回答这些问题不会获得任何额外分数。这是背包问题的最基本的实际应用。

To explain this problem a little easier, consider a test with 12 questions, 10 marks each, out of which only 10 should be attempted to get the maximum mark of 100. The test taker now must calculate the highest profitable questions – the one that he’s confident in – to achieve the maximum mark. However, he cannot attempt all the 12 questions since there will not be any extra marks awarded for those attempted answers. This is the most basic real-world application of the knapsack problem.

Knapsack Algorithm

作为输入，分数背包算法将要添加到背包中的物品的重量 (Wi) 和利润值 (Pi) 作为输入，而输出是添加到背包中的物品的子集，该子集不会超过限制并且具有最大利润。

The weights (Wi) and profit values (Pi) of the items to be added in the knapsack are taken as an input for the fractional knapsack algorithm and the subset of the items added in the knapsack without exceeding the limit and with maximum profit is achieved as the output.

Algorithm

  1. Consider all the items with their weights and profits mentioned respectively.

  2. Calculate Pi/Wi of all the items and sort the items in descending order based on their Pi/Wi values.

  3. Without exceeding the limit, add the items into the knapsack.

  4. If the knapsack can still store some weight, but the weights of other items exceed the limit, the fractional part of the next time can be added.

  5. Hence, giving it the name fractional knapsack problem.

Examples

  1. For the given set of items and the knapsack capacity of 10 kg, find the subset of the items to be added in the knapsack such that the profit is maximum.

Solution

Step 1

Step 1

给定，n = 5

Given, n = 5

Wi = {3, 3, 2, 5, 1}
Pi = {10, 15, 10, 12, 8}

计算所有项目的 Pi/Wi

Calculate Pi/Wi for all the items

Step 2

Step 2

根据 Pi/Wi 对所有项目进行降序排列

Arrange all the items in descending order based on Pi/Wi

Step 3

Step 3

在不超过背包容量的情况下，将物品放入背包中以获得最大利润。

Without exceeding the knapsack capacity, insert the items in the knapsack with maximum profit.

Knapsack = {5, 2, 3}

但是，背包仍然可以容纳 4 公斤的重量，但是下一个重量为 5 公斤的物品将超过容量。因此，将在背包中仅添加 5 公斤的 4 公斤重量。

However, the knapsack can still hold 4 kg weight, but the next item having 5 kg weight will exceed the capacity. Therefore, only 4 kg weight of the 5 kg will be added in the knapsack.

因此，背包的重量 = [(1 * 1) + (1 * 3) + (1 * 2) + (4/5 * 5)] = 10，最大利润 = [(1 * 8) + (1 * 15) + ( 1 * 10) + (4/5 * 20)] = 37。

Hence, the knapsack holds the weights = [(1 * 1) + (1 * 3) + (1 * 2) + (4/5 * 5)] = 10, with maximum profit of [(1 * 8) + (1 * 15) + (1 * 10) + (4/5 * 20)] = 37.

Example

以下是使用贪心算法的分数背包算法的最终实现 −

Following is the final implementation of Fractional Knapsack Algorithm using Greedy Approach −

Applications

背包问题在现实世界的许多应用中只有几个 −

Few of the many real-world applications of the knapsack problem are −

  1. Cutting raw materials without losing too much material

  2. Picking through the investments and portfolios

  3. Selecting assets of asset-backed securitization

  4. Generating keys for the Merkle-Hellman algorithm

  5. Cognitive Radio Networks

  6. Power Allocation

  7. Network selection for mobile nodes

  8. Cooperative wireless communication