15.2 Fractional Knapsack Problem¶

Question

Given $n$ items, where the weight of the $i$-th item is $wgt[i-1]$ and its value is $val[i-1]$, and a knapsack with capacity $cap$. Each item can be selected only once, but a fraction of an item may be selected, with its value proportional to the selected weight. What is the maximum total value that can be placed in the knapsack under the capacity constraint? An example is shown in Figure 15-3.

$Example data for the fractional knapsack problem$

Figure 15-3 Example data for the fractional knapsack problem

The fractional knapsack problem is very similar overall to the 0-1 knapsack problem, with states including the current item $i$ and capacity $c$, and the goal being to maximize value under the limited knapsack capacity.

The difference is that this problem allows selecting only a fraction of an item. As shown in Figure 15-4, we can split an item arbitrarily and compute its value in proportion to the selected weight.

For item $i$, its value per unit weight is $val[i-1] / wgt[i-1]$, referred to as unit value.
Suppose we put a portion of item $i$ with weight $w$ into the knapsack, then the value added to the knapsack is $w \times val[i-1] / wgt[i-1]$.

Value of items per unit weight

Figure 15-4 Value of items per unit weight

1. Greedy Strategy Determination¶

Maximizing the total value in the knapsack essentially means prioritizing items with higher value per unit weight. From this observation, we can derive the greedy strategy shown in Figure 15-5.

Sort items by unit value from high to low.
Iterate through all items, greedily selecting the item with the highest unit value in each round.
If the remaining knapsack capacity is insufficient, use a portion of the current item to fill the knapsack.

$Greedy strategy for the fractional knapsack problem$

Figure 15-5 Greedy strategy for the fractional knapsack problem

2. Code Implementation¶

We define an Item class so that items can be sorted by unit value. We then iterate through the sorted items greedily, stopping once the knapsack is full and returning the result:

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRuby

fractional_knapsack.py

class Item:
    """Item"""

    def __init__(self, w: int, v: int):
        self.w = w  # Item weight
        self.v = v  # Item value

def fractional_knapsack(wgt: list[int], val: list[int], cap: int) -> int:
    """Fractional knapsack: Greedy algorithm"""
    # Create item list with two attributes: weight, value
    items = [Item(w, v) for w, v in zip(wgt, val)]
    # Sort by unit value item.v / item.w from high to low
    items.sort(key=lambda item: item.v / item.w, reverse=True)
    # Loop for greedy selection
    res = 0
    for item in items:
        if item.w <= cap:
            # If remaining capacity is sufficient, put the entire current item into the knapsack
            res += item.v
            cap -= item.w
        else:
            # If remaining capacity is insufficient, put part of the current item into the knapsack
            res += (item.v / item.w) * cap
            # No remaining capacity, so break out of the loop
            break
    return res

fractional_knapsack.cpp

/* Item */
class Item {
  public:
    int w; // Item weight
    int v; // Item value

    Item(int w, int v) : w(w), v(v) {
    }
};

/* Fractional knapsack: Greedy algorithm */
double fractionalKnapsack(vector<int> &wgt, vector<int> &val, int cap) {
    // Create item list with two attributes: weight, value
    vector<Item> items;
    for (int i = 0; i < wgt.size(); i++) {
        items.push_back(Item(wgt[i], val[i]));
    }
    // Sort by unit value item.v / item.w from high to low
    sort(items.begin(), items.end(), [](Item &a, Item &b) { return (double)a.v / a.w > (double)b.v / b.w; });
    // Loop for greedy selection
    double res = 0;
    for (auto &item : items) {
        if (item.w <= cap) {
            // If remaining capacity is sufficient, put the entire current item into the knapsack
            res += item.v;
            cap -= item.w;
        } else {
            // If remaining capacity is insufficient, put part of the current item into the knapsack
            res += (double)item.v / item.w * cap;
            // No remaining capacity, so break out of the loop
            break;
        }
    }
    return res;
}

fractional_knapsack.java

/* Item */
class Item {
    int w; // Item weight
    int v; // Item value

    public Item(int w, int v) {
        this.w = w;
        this.v = v;
    }
}

/* Fractional knapsack: Greedy algorithm */
double fractionalKnapsack(int[] wgt, int[] val, int cap) {
    // Create item list with two attributes: weight, value
    Item[] items = new Item[wgt.length];
    for (int i = 0; i < wgt.length; i++) {
        items[i] = new Item(wgt[i], val[i]);
    }
    // Sort by unit value item.v / item.w from high to low
    Arrays.sort(items, Comparator.comparingDouble(item -> -((double) item.v / item.w)));
    // Loop for greedy selection
    double res = 0;
    for (Item item : items) {
        if (item.w <= cap) {
            // If remaining capacity is sufficient, put the entire current item into the knapsack
            res += item.v;
            cap -= item.w;
        } else {
            // If remaining capacity is insufficient, put part of the current item into the knapsack
            res += (double) item.v / item.w * cap;
            // No remaining capacity, so break out of the loop
            break;
        }
    }
    return res;
}

fractional_knapsack.cs

/* Item */
class Item(int w, int v) {
    public int w = w; // Item weight
    public int v = v; // Item value
}

/* Fractional knapsack: Greedy algorithm */
double FractionalKnapsack(int[] wgt, int[] val, int cap) {
    // Create item list with two attributes: weight, value
    Item[] items = new Item[wgt.Length];
    for (int i = 0; i < wgt.Length; i++) {
        items[i] = new Item(wgt[i], val[i]);
    }
    // Sort by unit value item.v / item.w from high to low
    Array.Sort(items, (x, y) => (y.v / y.w).CompareTo(x.v / x.w));
    // Loop for greedy selection
    double res = 0;
    foreach (Item item in items) {
        if (item.w <= cap) {
            // If remaining capacity is sufficient, put the entire current item into the knapsack
            res += item.v;
            cap -= item.w;
        } else {
            // If remaining capacity is insufficient, put part of the current item into the knapsack
            res += (double)item.v / item.w * cap;
            // No remaining capacity, so break out of the loop
            break;
        }
    }
    return res;
}

fractional_knapsack.go

/* Item */
type Item struct {
    w int // Item weight
    v int // Item value
}

/* Fractional knapsack: Greedy algorithm */
func fractionalKnapsack(wgt []int, val []int, cap int) float64 {
    // Create item list with two attributes: weight, value
    items := make([]Item, len(wgt))
    for i := 0; i < len(wgt); i++ {
        items[i] = Item{wgt[i], val[i]}
    }
    // Sort by unit value item.v / item.w from high to low
    sort.Slice(items, func(i, j int) bool {
        return float64(items[i].v)/float64(items[i].w) > float64(items[j].v)/float64(items[j].w)
    })
    // Loop for greedy selection
    res := 0.0
    for _, item := range items {
        if item.w <= cap {
            // If remaining capacity is sufficient, put the entire current item into the knapsack
            res += float64(item.v)
            cap -= item.w
        } else {
            // If remaining capacity is insufficient, put part of the current item into the knapsack
            res += float64(item.v) / float64(item.w) * float64(cap)
            // No remaining capacity, so break out of the loop
            break
        }
    }
    return res
}

fractional_knapsack.swift

/* Item */
class Item {
    var w: Int // Item weight
    var v: Int // Item value

    init(w: Int, v: Int) {
        self.w = w
        self.v = v
    }
}

/* Fractional knapsack: Greedy algorithm */
func fractionalKnapsack(wgt: [Int], val: [Int], cap: Int) -> Double {
    // Create item list with two attributes: weight, value
    var items = zip(wgt, val).map { Item(w: $0, v: $1) }
    // Sort by unit value item.v / item.w from high to low
    items.sort { -(Double($0.v) / Double($0.w)) < -(Double($1.v) / Double($1.w)) }
    // Loop for greedy selection
    var res = 0.0
    var cap = cap
    for item in items {
        if item.w <= cap {
            // If remaining capacity is sufficient, put the entire current item into the knapsack
            res += Double(item.v)
            cap -= item.w
        } else {
            // If remaining capacity is insufficient, put part of the current item into the knapsack
            res += Double(item.v) / Double(item.w) * Double(cap)
            // No remaining capacity, so break out of the loop
            break
        }
    }
    return res
}

fractional_knapsack.js

/* Item */
class Item {
    constructor(w, v) {
        this.w = w; // Item weight
        this.v = v; // Item value
    }
}

/* Fractional knapsack: Greedy algorithm */
function fractionalKnapsack(wgt, val, cap) {
    // Create item list with two attributes: weight, value
    const items = wgt.map((w, i) => new Item(w, val[i]));
    // Sort by unit value item.v / item.w from high to low
    items.sort((a, b) => b.v / b.w - a.v / a.w);
    // Loop for greedy selection
    let res = 0;
    for (const item of items) {
        if (item.w <= cap) {
            // If remaining capacity is sufficient, put the entire current item into the knapsack
            res += item.v;
            cap -= item.w;
        } else {
            // If remaining capacity is insufficient, put part of the current item into the knapsack
            res += (item.v / item.w) * cap;
            // No remaining capacity, so break out of the loop
            break;
        }
    }
    return res;
}

fractional_knapsack.ts

/* Item */
class Item {
    w: number; // Item weight
    v: number; // Item value

    constructor(w: number, v: number) {
        this.w = w;
        this.v = v;
    }
}

/* Fractional knapsack: Greedy algorithm */
function fractionalKnapsack(wgt: number[], val: number[], cap: number): number {
    // Create item list with two attributes: weight, value
    const items: Item[] = wgt.map((w, i) => new Item(w, val[i]));
    // Sort by unit value item.v / item.w from high to low
    items.sort((a, b) => b.v / b.w - a.v / a.w);
    // Loop for greedy selection
    let res = 0;
    for (const item of items) {
        if (item.w <= cap) {
            // If remaining capacity is sufficient, put the entire current item into the knapsack
            res += item.v;
            cap -= item.w;
        } else {
            // If remaining capacity is insufficient, put part of the current item into the knapsack
            res += (item.v / item.w) * cap;
            // No remaining capacity, so break out of the loop
            break;
        }
    }
    return res;
}

fractional_knapsack.dart

/* Item */
class Item {
  int w; // Item weight
  int v; // Item value

  Item(this.w, this.v);
}

/* Fractional knapsack: Greedy algorithm */
double fractionalKnapsack(List<int> wgt, List<int> val, int cap) {
  // Create item list with two attributes: weight, value
  List<Item> items = List.generate(wgt.length, (i) => Item(wgt[i], val[i]));
  // Sort by unit value item.v / item.w from high to low
  items.sort((a, b) => (b.v / b.w).compareTo(a.v / a.w));
  // Loop for greedy selection
  double res = 0;
  for (Item item in items) {
    if (item.w <= cap) {
      // If remaining capacity is sufficient, put the entire current item into the knapsack
      res += item.v;
      cap -= item.w;
    } else {
      // If remaining capacity is insufficient, put part of the current item into the knapsack
      res += item.v / item.w * cap;
      // No remaining capacity, so break out of the loop
      break;
    }
  }
  return res;
}

fractional_knapsack.rs

/* Item */
struct Item {
    w: i32, // Item weight
    v: i32, // Item value
}

impl Item {
    fn new(w: i32, v: i32) -> Self {
        Self { w, v }
    }
}

/* Fractional knapsack: Greedy algorithm */
fn fractional_knapsack(wgt: &[i32], val: &[i32], mut cap: i32) -> f64 {
    // Create item list with two attributes: weight, value
    let mut items = wgt
        .iter()
        .zip(val.iter())
        .map(|(&w, &v)| Item::new(w, v))
        .collect::<Vec<Item>>();
    // Sort by unit value item.v / item.w from high to low
    items.sort_by(|a, b| {
        (b.v as f64 / b.w as f64)
            .partial_cmp(&(a.v as f64 / a.w as f64))
            .unwrap()
    });
    // Loop for greedy selection
    let mut res = 0.0;
    for item in &items {
        if item.w <= cap {
            // If remaining capacity is sufficient, put the entire current item into the knapsack
            res += item.v as f64;
            cap -= item.w;
        } else {
            // If remaining capacity is insufficient, put part of the current item into the knapsack
            res += item.v as f64 / item.w as f64 * cap as f64;
            // No remaining capacity, so break out of the loop
            break;
        }
    }
    res
}

fractional_knapsack.c

/* Item */
typedef struct {
    int w; // Item weight
    int v; // Item value
} Item;

/* Fractional knapsack: Greedy algorithm */
float fractionalKnapsack(int wgt[], int val[], int itemCount, int cap) {
    // Create item list with two attributes: weight, value
    Item *items = malloc(sizeof(Item) * itemCount);
    for (int i = 0; i < itemCount; i++) {
        items[i] = (Item){.w = wgt[i], .v = val[i]};
    }
    // Sort by unit value item.v / item.w from high to low
    qsort(items, (size_t)itemCount, sizeof(Item), sortByValueDensity);
    // Loop for greedy selection
    float res = 0.0;
    for (int i = 0; i < itemCount; i++) {
        if (items[i].w <= cap) {
            // If remaining capacity is sufficient, put the entire current item into the knapsack
            res += items[i].v;
            cap -= items[i].w;
        } else {
            // If remaining capacity is insufficient, put part of the current item into the knapsack
            res += (float)cap / items[i].w * items[i].v;
            cap = 0;
            break;
        }
    }
    free(items);
    return res;
}

fractional_knapsack.kt

/* Item */
class Item(
    val w: Int, // Item
    val v: Int  // Item value
)

/* Fractional knapsack: Greedy algorithm */
fun fractionalKnapsack(wgt: IntArray, _val: IntArray, c: Int): Double {
    // Create item list with two attributes: weight, value
    var cap = c
    val items = arrayOfNulls<Item>(wgt.size)
    for (i in wgt.indices) {
        items[i] = Item(wgt[i], _val[i])
    }
    // Sort by unit value item.v / item.w from high to low
    items.sortBy { item: Item? -> -(item!!.v.toDouble() / item.w) }
    // Loop for greedy selection
    var res = 0.0
    for (item in items) {
        if (item!!.w <= cap) {
            // If remaining capacity is sufficient, put the entire current item into the knapsack
            res += item.v
            cap -= item.w
        } else {
            // If remaining capacity is insufficient, put part of the current item into the knapsack
            res += item.v.toDouble() / item.w * cap
            // No remaining capacity, so break out of the loop
            break
        }
    }
    return res
}

fractional_knapsack.rb

### Item ###
class Item
  attr_accessor :w # Item weight
  attr_accessor :v # Item value

  def initialize(w, v)
    @w = w
    @v = v
  end
end

### Fractional knapsack: greedy ###
def fractional_knapsack(wgt, val, cap)
  # Create item list with two attributes: weight, value
  items = wgt.each_with_index.map { |w, i| Item.new(w, val[i]) }
  # Sort by unit value item.v / item.w from high to low
  items.sort! { |a, b| (b.v.to_f / b.w) <=> (a.v.to_f / a.w) }
  # Loop for greedy selection
  res = 0
  for item in items
    if item.w <= cap
      # If remaining capacity is sufficient, put the entire current item into the knapsack
      res += item.v
      cap -= item.w
    else
      # If remaining capacity is insufficient, put part of the current item into the knapsack
      res += (item.v.to_f / item.w) * cap
      # No remaining capacity, so break out of the loop
      break
    end
  end
  res
end

Built-in sorting algorithms usually take $O(n \log n)$ time, and their space complexity is usually $O(\log n)$ or $O(n)$, depending on the specific implementation of the programming language.

Apart from sorting, in the worst case the entire item list needs to be traversed, therefore the time complexity is $O(n)$, where $n$ is the number of items.

Since an Item object list is initialized, the space complexity is $O(n)$.

3. Correctness Proof¶

We use proof by contradiction. Suppose item $x$ has the highest unit value, and some algorithm produces an optimal value res, but the resulting solution does not include item $x$.

Now remove one unit of weight from any item in the knapsack and replace it with one unit of weight from item $x$. Since item $x$ has the highest unit value, the total value after the replacement must be greater than res. This contradicts the assumption that res is optimal, proving that any optimal solution must include item $x$.

We can construct the same contradiction for the other items in the solution as well. In summary, items with higher unit value are always the better choice, which proves that the greedy strategy is effective.

As shown in Figure 15-6, if we treat item weight and unit value as the horizontal and vertical axes of a two-dimensional chart, then the fractional knapsack problem can be viewed as "finding the maximum area enclosed within a bounded interval on the horizontal axis." This analogy helps explain the effectiveness of the greedy strategy from a geometric perspective.

$Geometric representation of the fractional knapsack problem$

Figure 15-6 Geometric representation of the fractional knapsack problem

15.2 Fractional Knapsack Problem¶

1. Greedy Strategy Determination¶

2. Code Implementation¶

3. Correctness Proof¶

Feel free to drop your insights, questions or suggestions