ปัญหาเป้เศษส่วน

มีรายการของรายการ แต่ละรายการมีค่าและน้ำหนักของตัวเอง สามารถวางสิ่งของในเป้ที่น้ำหนักสูงสุดคือ W ปัญหาคือการหาน้ำหนักที่น้อยกว่าหรือเท่ากับ W และค่าจะถูกขยายให้ใหญ่สุด

ปัญหาเป้มีสองประเภท

• 0 – 1 เป้
• เป้เศษส่วน

สำหรับเป้ 0 – 1 สิ่งของไม่สามารถแบ่งออกเป็นชิ้นเล็ก ๆ และสำหรับเป้เศษส่วน สิ่งของสามารถแตกเป็นชิ้นเล็ก ๆ ได้

เราจะมาพูดถึงปัญหาของเป้แบบเศษส่วน

ความซับซ้อนของเวลาของอัลกอริทึมนี้คือ O(n Log n)

อินพุตและเอาต์พุต

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

อัลกอริทึม

fractionalKnapsack(weight, itemList, n)

อินพุต - น้ำหนักสูงสุดของเป้ รายการสินค้า และจำนวนรายการ

ผลลัพธ์: ค่าสูงสุดที่ได้รับ

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

ตัวอย่าง

#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);
}

ผลลัพธ์

Maximum value: 240