分数背包问题

Table of content
上一页
下一页

背包问题陈述如下：给定一组物品，包含重量和利润值，必须确定要添加到背包中的物品子集，以便物品的总重量不超过背包的限制，并且其总利润值最大。

这是最流行的问题之一，它采用贪心算法来解决。它被称为**分数背包问题**。

为了更容易解释这个问题，请考虑一个包含12个问题，每个问题10分的测试，其中只有10个问题需要解答才能获得100分的最高分。现在，测试者必须计算最有价值的问题——他最有把握的问题——以获得最高分。但是，他不能尝试所有12个问题，因为尝试回答的答案不会获得额外的分数。这是背包问题最基本、最现实的应用之一。

背包算法

要添加到背包中的物品的重量（Wi）和利润值（Pi）作为分数背包算法的输入，而添加到背包中的物品子集（不超过限制且利润最大）作为输出。

算法

  • 考虑所有物品及其各自的重量和利润。

  • 计算所有物品的Pi/Wi，并根据它们的Pi/Wi值按降序对物品进行排序。

  • 在不超过限制的情况下，将物品添加到背包中。

  • 如果背包仍然可以存放一些重量，但其他物品的重量超过了限制，则可以添加下一个物品的分数部分。

  • 因此，将其命名为分数背包问题。

示例

  • 对于给定的物品集和10公斤的背包容量，找到要添加到背包中的物品子集，使得利润最大。

物品 1 2 3 4 5
重量（公斤） 3 3 2 5 1
利润 10 15 10 12 8

解决方案

步骤1

给定，n = 5

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

计算所有物品的Pi/Wi

物品 1 2 3 4 5
重量（公斤） 3 3 2 5 1
利润 10 15 10 20 8
Pi/Wi 3.3 5 5 4 8

步骤2

根据Pi/Wi按降序排列所有物品。

物品 5 2 3 4 1
重量（公斤） 1 3 2 5 3
利润 8 15 10 20 10
Pi/Wi 8 5 5 4 3.3

步骤3

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

Knapsack = {5, 2, 3}

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

物品 5 2 3 4 1
重量（公斤） 1 3 2 5 3
利润 8 15 10 20 10
背包 1 1 1 4/5 0

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

示例

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

C C++ Java Python
#include <stdio.h>
int n = 5;
int p[10] = {3, 3, 2, 5, 1};
int w[10] = {10, 15, 10, 12, 8};
int W = 10;
int main(){
   int cur_w;
   float tot_v;
   int i, maxi;
   int used[10];
   for (i = 0; i < n; ++i)
      used[i] = 0;
   cur_w = W;
   while (cur_w > 0) {
      maxi = -1;
      for (i = 0; i < n; ++i)
         if ((used[i] == 0) &&
               ((maxi == -1) || ((float)w[i]/p[i] > (float)w[maxi]/p[maxi])))
            maxi = i;
      used[maxi] = 1;
      cur_w -= p[maxi];
      tot_v += w[maxi];
      if (cur_w >= 0)
         printf("Added object %d (%d, %d) completely in the bag. Space left: %d.\n", maxi + 1, w[maxi], p[maxi], cur_w);
      else {
         printf("Added %d%% (%d, %d) of object %d in the bag.\n", (int)((1 + (float)cur_w/p[maxi]) * 100), w[maxi], p[maxi], maxi + 1);
         tot_v -= w[maxi];
         tot_v += (1 + (float)cur_w/p[maxi]) * w[maxi];
      }
   }
   printf("Filled the bag with objects worth %.2f.\n", tot_v);
   return 0;
}

输出

Added object 5 (8, 1) completely in the bag. Space left: 9.
Added object 2 (15, 3) completely in the bag. Space left: 6.
Added object 3 (10, 2) completely in the bag. Space left: 4.
Added object 1 (10, 3) completely in the bag. Space left: 1.
Added 19% (12, 5) of object 4 in the bag.
Filled the bag with objects worth 45.40.

#include <iostream>
int n = 5;
int p[10] = {3, 3, 2, 5, 1};
int w[10] = {10, 15, 10, 12, 8};
int W = 10;
int main(){
   int cur_w;
   float tot_v;
   int i, maxi;
   int used[10];
   for (i = 0; i < n; ++i)
      used[i] = 0;
   cur_w = W;
   while (cur_w > 0) {
      maxi = -1;
      for (i = 0; i < n; ++i)
         if ((used[i] == 0) &&
               ((maxi == -1) || ((float)w[i]/p[i] > (float)w[maxi]/p[maxi])))
            maxi = i;
      used[maxi] = 1;
      cur_w -= p[maxi];
      tot_v += w[maxi];
      if (cur_w >= 0)
         printf("Added object %d (%d, %d) completely in the bag. Space left: %d.\n", maxi + 1, w[maxi], p[maxi], cur_w);
      else {
         printf("Added %d%% (%d, %d) of object %d in the bag.\n", (int)((1 + (float)cur_w/p[maxi]) * 100), w[maxi], p[maxi], maxi + 1);
         tot_v -= w[maxi];
         tot_v += (1 + (float)cur_w/p[maxi]) * w[maxi];
      }
   }
   printf("Filled the bag with objects worth %.2f.\n", tot_v);
   return 0;
}

输出

Added object 5 (8, 1) completely in the bag. Space left: 9.
Added object 2 (15, 3) completely in the bag. Space left: 6.
Added object 3 (10, 2) completely in the bag. Space left: 4.
Added object 1 (10, 3) completely in the bag. Space left: 1.
Added 19% (12, 5) of object 4 in the bag.
Filled the bag with objects worth 45.40.

public class Main {
   static int n = 5;
   static int p[] = {3, 3, 2, 5, 1};
   static int w[] = {10, 15, 10, 12, 8};
   static int W = 10;
   public static void main(String args[]) {
      int cur_w;
      float tot_v = 0;
      int i, maxi;
      int used[] = new int[10];
      for (i = 0; i < n; ++i)
         used[i] = 0;
      cur_w = W;
      while (cur_w > 0) {
         maxi = -1;
         for (i = 0; i < n; ++i)
            if ((used[i] == 0) &&
                  ((maxi == -1) || ((float)w[i]/p[i] > (float)w[maxi]/p[maxi])))
               maxi = i;
         used[maxi] = 1;
         cur_w -= p[maxi];
         tot_v += w[maxi];
         if (cur_w >= 0)
            System.out.println("Added object " + maxi + 1 + " (" + w[maxi] + "," + p[maxi] + ") completely in the bag. Space left: " + cur_w);
         else {
            System.out.println("Added " + ((int)((1 + (float)cur_w/p[maxi]) * 100)) + "% (" + w[maxi] + "," + p[maxi] + ") of object " + (maxi + 1) + " in the bag.");
            tot_v -= w[maxi];
            tot_v += (1 + (float)cur_w/p[maxi]) * w[maxi];
         }
      }
      System.out.println("Filled the bag with objects worth " + tot_v);
   }
}

输出

Added object 41 (8,1) completely in the bag. Space left: 9
Added object 11 (15,3) completely in the bag. Space left: 6
Added object 21 (10,2) completely in the bag. Space left: 4
Added object 01 (10,3) completely in the bag. Space left: 1
Added 19% (12,5) of object 4 in the bag.
Filled the bag with objects worth 45.4

n = 5
p = [3, 3, 2, 5, 1]
w = [10, 15, 10, 12, 8]
W = 10
cur_w = W
tot_v = 0
used = [0] * 10
for i in range(n):
    used[i] = 0
while cur_w > 0:
    maxi = -1
    for i in range(n):
        if (used[i] == 0) and ((maxi == -1) or ((w[i] / p[i]) > (w[maxi] / p[maxi]))):
            maxi = i
    used[maxi] = 1
    cur_w -= p[maxi]
    tot_v += w[maxi]
    if cur_w >= 0:
        print(f"Added object {maxi + 1} ({w[maxi]}, {p[maxi]}) completely in the bag. Space left: {cur_w}.")
    else:
        percent_added = int((1 + (cur_w / p[maxi])) * 100)
        print(f"Added {percent_added}% ({w[maxi]}, {p[maxi]}) of object {maxi + 1} in the bag.")
        tot_v -= w[maxi]
        tot_v += (1 + (cur_w / p[maxi])) * w[maxi]
print(f"Filled the bag with objects worth {tot_v:.2f}.")

输出

Added object 5 (8, 1) completely in the bag. Space left: 9.
Added object 2 (15, 3) completely in the bag. Space left: 6.
Added object 3 (10, 2) completely in the bag. Space left: 4.
Added object 1 (10, 3) completely in the bag. Space left: 1.
Added 19% (12, 5) of object 4 in the bag.
Filled the bag with objects worth 45.40.

应用

背包问题的许多实际应用包括：

  • 切割原材料，尽量减少材料浪费

  • 挑选投资组合和资产

  • 选择资产支持证券化的资产

  • 生成Merkle-Hellman算法的密钥

  • 认知无线电网络

  • 功率分配

  • 移动节点网络选择

  • 协作无线通信

打印页面
上一页
下一页
广告