设计与分析 - 分数背包

背包问题指出 - 给定一组物品、持有重量和利润值，必须确定要添加到背包中的物品的子集，使得物品的总重量不得超过背包的限制，并且其总利润值最大。

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

为了更容易地解释这个问题，考虑一个有 12 个问题的测试，每个问题 10 分，其中只有 10 个问题应该尝试以获得最高分 100 分。现在，考生必须计算出利润最高的问题 - 他认为是最有利的问题。有信心——取得最高分。然而，他无法尝试全部 12 个问题，因为这些尝试的答案不会获得任何额外分数。这是背包问题最基本的现实应用。

背包算法

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

算法

  • 考虑所有物品及其分别提到的重量和利润。

  • 计算所有项目的 P i /W i并根据其 P i /W i值按降序对项目进行排序。

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

  • 如果背包还能储存一些重量，但其他物品的重量超过限制，则可以添加下次的小数部分。

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

例子

  • 对于给定的一组物品和 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}

计算所有项目的P i /W i

项目 1 2 3 4 5
重量（公斤） 3 3 2 5 1
利润 10 15 10 20 8
皮/维_ 3.3 5 5 4 8

第2步

根据 P i /W i将所有项目按降序排列

项目 5 2 3 4 1
重量（公斤） 1 3 2 5 3
利润 8 15 10 20 10
皮/维_ 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 算法生成密钥

  • 认知无线电网络

  • 功率分配

  • 移动节点的网络选择

协作无线通信