Skip to content
Welcome to contribute to Chinese-to-English translation! For more details, please refer to CONTRIBUTING.md.

# 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.

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.

1. For item \(i\), its value per unit weight is \(val[i-1] / wgt[i-1]\), referred to as unit value.
2. 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]\).

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.

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

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:

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
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.

Figure 15-6 Geometric representation of the fractional knapsack problem

##### Feel free to drop your insights, questions or suggestions