Fractional Knapsack Problem (ปัญหาเป้แบ่งเศษได้)

Fractional Knapsack Problem เป็นปัญหาเพิ่มค่าสูงสุด (Maximize Value) โดยมีข้อจำกัดน้ำหนัก (Weight Capacity) W แตกต่างจาก 0-1 Knapsack ที่ สามารถแบ่งสิ่งของเป็นเศษส่วนได้

ความแตกต่าง 0-1 vs Fractional

กลยุทธ์ Greedy

1. คำนวณ Value/Weight Ratio (คุณค่าต่อหน่วยน้ำหนัก) ของแต่ละสิ่งของ
2. เรียงสิ่งของตาม Ratio มากไปน้อย
3. หยิบสิ่งของตามลำดับ: ถ้าน้ำหนักพอ → เอาทั้งชิ้น, ไม่พอ → เอาเศษส่วนที่พอ
4. หยุดเมื่อเป้เต็ม

ตัวอย่างข้อมูล

Capacity W = 50
Items: (Value, Weight)
  Item 1: (60, 10)  Ratio = 6.0
  Item 2: (100, 20) Ratio = 5.0
  Item 3: (120, 30) Ratio = 4.0

Sorted by Ratio: Item1, Item2, Item3

Take Item1 (10kg): Value 60, Remaining 40kg
Take Item2 (20kg): Value 100, Remaining 20kg
Take Item3 (20/30): Value 120*(20/30)=80, Remaining 0kg

Total Value = 60 + 100 + 80 = 240

อัลกอริทึม (Pseudocode)

fractionalKnapsack(W, items[], n)
  sort items by value/weight ratio descending
  currWeight = 0
  totalValue = 0

  for each item in items:
    if currWeight + item.weight <= W:
      currWeight += item.weight
      totalValue += item.value
    else:
      remaining = W - currWeight
      totalValue += item.value * (remaining / item.weight)
      break

  return totalValue

ตัวอย่างโค้ด C++

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

struct Item {
    int value, weight;
};

bool cmp(Item a, Item b) {
    double r1 = (double)a.value / a.weight;
    double r2 = (double)b.value / b.weight;
    return r1 > r2;
}

double fractionalKnapsack(int W, Item items[], int n) {
    sort(items, items + n, cmp);

    int currWeight = 0;
    double totalValue = 0.0;

    for (int i = 0; i < n; i++) {
        if (currWeight + items[i].weight <= W) {
            currWeight += items[i].weight;
            totalValue += items[i].value;
        } else {
            int remaining = W - currWeight;
            totalValue += items[i].value * ((double)remaining / items[i].weight);
            break;
        }
    }
    return totalValue;
}

int main() {
    int W = 50;
    Item items[] = {{60, 10}, {100, 20}, {120, 30}};
    int n = 3;
    cout << "Maximum value: " << fractionalKnapsack(W, items, n) << endl;
}

คุณสมบัติ

• Greedy Choice Property: เลือก Ratio สูงสุดทีละขั้นตอนได้คำตอบ Optimal
• Optimal Substructure: ปัญหาย่อยก็เป็น Fractional Knapsack เช่นกัน
• Time: O(n log n) จากการเรียงลำดับ

การประยุกต์ใช้

• การจัดสรรทรัพยากร (Resource Allocation)
• Portfolio Optimization (ถ้าแบ่งหุ้นได้)
• Bandwidth Allocation
• Cutting Stock Problems