分數揹包問題

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演算法的金鑰

  • 認知無線電網路

  • 功率分配

  • 移動節點網路選擇

  • 協作無線通訊

列印頁面
上一頁
下一頁
廣告