Bài toán Fractional Knapsack (Cái ba lô phân số)

Cho danh sách vật phẩm, mỗi vật có giá trị (value) và trọng lượng (weight). Cái ba lô giới hạn trọng lượng W. Tìm tập vật phẩm (có thể chia nhỏ) để tổng trọng lượng ≤ W và tổng giá trị lớn nhất.

Hai loại Knapsack: 0-1 (không chia nhỏ) và Fractional (chia nhỏ được).

Độ phức tạp: O(n log n) do sắp xếp.

Input và Output

Input: Max weight = 50. Items: {(60,10), (100,20), (120,30)}
Output: Max value: 240 (lấy vật weight 20 và 30, phần của weight 10)

Thuật toán

fractionalKnapsack(weight, itemList, n)
Input: Trọng lượng tối đa, danh sách vật phẩm, số lượng
Output: Giá trị tối đa

Begin
  sắp xếp itemList theo tỷ lệ value/weight giảm dần
  currentWeight := 0, knapsackVal := 0
  for item i in list do
    if currentWeight + weight[i] <= weight then
      currentWeight += weight[i]
      knapsackVal += value[i]
    else
      remaining := weight - currentWeight
      knapsackVal += value[i] * (remaining / weight[i])
      break
    done
  done
End

Ví dụ (C++)

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

struct Item { int value, weight; };

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

double fractionalKnapsack(int W, Item items[], int n) {
    sort(items, items+n, cmp);
    int currW = 0; double val = 0.0;
    for(int i=0;i
Kết quả
Max value: 240
Giải thích: Tỷ lệ: 60/10=6, 100/20=5, 120/30=4. Lấy hết item 1 (10kg, 60), item 2 (20kg, 100) → 30kg, 160. Còn 20kg, lấy 2/3 item 3 → +80 = 240. Fractional Knapsack luôn cho giải pháp tối ưu bằng Greedy (khác 0-1 Knapsack cần DP).