Vấn đề về Fractional Knapsack

Một danh sách các mặt hàng được đưa ra, mỗi mặt hàng có giá trị và trọng lượng riêng. Các vật phẩm có thể được đặt trong một cái ba lô có giới hạn trọng lượng tối đa là W. Vấn đề là tìm trọng lượng nhỏ hơn hoặc bằng W và giá trị là lớn nhất.

Có hai loại vấn đề Knapsack.

• 0 - 1 Knapsack
• Fractional Knapsack

Đối với Knapsack 0 - 1, các mục không thể được chia thành nhiều phần nhỏ hơn và đối với túi đựng phân đoạn, các mục có thể được chia thành nhiều phần nhỏ hơn.

Ở đây chúng ta sẽ thảo luận về vấn đề cái túi phân số.

Độ phức tạp về thời gian của thuật toán này là O (n Log n).

Đầu vào và Đầu ra

Input:
Maximum weight = 50. List of items with value and weight.
{(60, 10), (100, 20), (120, 30)}
Output:
Maximum value: 240
By taking the items of weight 20 and 30

Thuật toán

fractionalKnapsack(weight, itemList, n)

Đầu vào - trọng lượng tối đa của gói, danh sách các mặt hàng và số lượng mặt hàng

Đầu ra: Giá trị lớn nhất thu được.

Begin
   sort the item list based on the ration of value and weight
   currentWeight := 0
   knapsackVal := 0

   for all items i in the list do
      if currentWeight + weight of item[i] < weight then
         currentWeight := currentWeight + weight of item[i]
         knapsackVal := knapsackVal + value of item[i]
      else
         remaining := weight – currentWeight
         knapsackVal “= knapsackVal + value of item[i] * (remaining/weight of item[i])
         break the loop
   done
End

Ví dụ

#include <iostream>
#include<algorithm>
using namespace std;

struct item {
   int value, weight;
};

bool cmp(struct item a, struct item b) {     //compare item a and item b based on the ration of value and weight
   double aRatio = (double)a.value / a.weight;
   double bRatio = (double)b.value / b.weight;
   return aRatio > bRatio;
}

double fractionalKnapsack(int weight, item itemList[], int n) {
   sort(itemList, itemList + n, cmp);      //sort item list using compare function
   int currWeight = 0;        // Current weight in knapsack
   double knapsackVal = 0.0;

   for (int i = 0; i < n; i++) {       //check through all items
      if (currWeight + itemList[i].weight <= weight) {     //when the space is enough for selected item, add it
         currWeight += itemList[i].weight;
         knapsackVal += itemList[i].value;

      }else{       //when no place for whole item, break it into smaller parts
         int remaining = weight - currWeight;
         knapsackVal += itemList[i].value * ((double) remaining / itemList[i].weight);
         break;
      }
   }
   return knapsackVal;
}

int main() {
   int weight = 50;     // Weight of knapsack
   item itemList[] = {{60, 10}, {100, 20}, {120, 30}};
   int n = 3;
   cout << "Maximum value: " << fractionalKnapsack(weight, itemList, n);
}

Đầu ra

Maximum value: 240