Problem

Given the weights (w1, w2, ... wn) and values (v1, v2, ... vn) of n items, along with the capacity W of a knapsack, the task is to maximise the total value of the items in the knapsack.

Unlike the 0-1 Knapsack problem, where items cannot be divided, the Fractional Knapsack problem allows taking fractions of items. This means we can divide an item into smaller portions proportional to its weight and take only the fraction that fits in the remaining capacity of the knapsack.

Examples

Example 1

1
2
3
4
5
6
7

Input: weights = [10, 20, 30], values = [60, 100, 120], capacity = 50
Output: 240 (Maximum value)
Explanation:
- Item 1: take full weight (10) → Value 60 (used capacity: 10/50).
- Item 2: take full weight (20) → Value 100 (used capacity: 30/50).
- Item 3: take 2/3 of weight (20 out of 30) → Value 80 (used capacity: 50/50).
Total value = 60 + 100 + 80 = 240.

Example 2

1
2
3
4
5
6
7

Input: weights = [40, 10, 20], values = [100, 60, 120], capacity = 50
Output: 180 (Maximum value)
Explanation:
- Item 2: take full weight (10) → Value 60 (used capacity: 10/50).
- Item 3: take full weight (20) → Value 120 (used capacity: 30/50).
- Item 1: take 1/4 of weight (10 out of 40) → Value 25 (used capacity: 50/50).
Total value = 60 + 120 + 25 = 180.

Variations

In this article, we explored the Fractional Knapsack problem, where items can be divided to maximise value using a greedy approach. However, this is just one variation of the knapsack problem. When items cannot be divided, we move to the Discrete Knapsack problems, where each item is either taken entirely or left out. Discrete knapsack problems come in two types:

Additionally, there are special cases of the knapsack problem:

  • All items have equal weight: In this scenario, the goal is to maximise profit as all items weigh the same. Sorting items by value and then picking the highest-value items will solve this variant using a greedy approach.
  • All items have equal value: If all items have the same value, selecting as many items as possible within the weight limit becomes the target. Sorting items by size and selecting the smallest ones until the knapsack is full provides an efficient solution.

Another prominent instance of the knapsack problem is the Subset Sum Problem, where each item’s value is proportional to its size. For example, consider a collection of gold weights: heavier weights hold more value, and the goal is to fill the knapsack while minimising leftover space. Additionally, this problem appears in cases where you aim to achieve a specific total (C) as closely as possible.

However, this subset sum problem cannot be solved using a greedy algorithm because it is NP-complete. This means it belongs to a class of problems for which no known polynomial-time solutions exist unless P = NP is proven. It is often linked to the Subset Sum Problem and related algorithms like the Integer Partition Algorithm.

Solution

Method 1 - Brute Force

A brute-force approach would involve testing every possible subset with varying fractions, but this method is highly time-consuming.

Method 2 - Greedy

Reasoning and Intuition

An efficient way to solve the Fractional Knapsack problem is by using a greedy approach. The core idea is to prioritise items with the highest value-to-weight ratio (v[i]/w[i]) because they yield the most value per unit of weight. So, we compute the ratio of value/weight for each item, then sort all items based on this ratio in descending order. Items having higher ratios should be placed in the knapsack first, and only fractions of subsequent items are used to fill the remaining capacity, if necessary. This ensures that items contributing the highest value per unit of weight are prioritised.

Approach

  1. Calculate value-to-weight ratio: For each item, compute the ratio v[i]/w[i].
  2. Sort items by their ratio: Sort items in descending order of value-to-weight ratio.
  3. Fill the knapsack greedily:
    • Start with the first item and take it fully if weight allows.
    • If the knapsack does not have sufficient capacity, take a fraction proportional to the remaining space.
  4. Stop when the knapsack is full.

This greedy strategy ensures the maximum value is achieved.

Pseudocode

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

FractionalKnapsack(W, weights, values, n)
    Initialize A ← [0, 0, ..., 0]  // To store fractions of items taken
    Initialize V ← 0              // Total value accumulated

    Compute value-to-weight ratio for each item:
        ratio[i] ← values[i] / weights[i] for i = 1 to n
    
    Sort items by ratio[i] in descending order

    for i = 1 to n:
        if W == 0:
            return (V, A)         // If capacity is exhausted, return value and fractions
            
        a ← min(weights[i], W)   // Take the minimum of item's weight or remaining capacity
        V ← V + a * ratio[i]     // Add the value of the fraction to total value
        A[i] ← a / weights[i]    // Store the fraction of the taken item
        W ← W - a                // Reduce knapsack capacity by the weight taken
    
    return (V, A)                // Return total value and fractions taken

Sample run

Here is how it can work:

  1. Make a greedy choice: Pick as many items as possible with the highest value-to-weight ratio. For example, consider these items:
    • Item A: 20/4 = 5/unit
    • Item B: 18/3 = 6/unit
    • Item C: 14/2 = 7/unit Since item C offers the highest value per weight unit, it is chosen first, followed by item B and then item A as much as the capacity allows.
  2. Ensure it’s an optimal move: Any item can be divided into smaller fractions of weight with proportional value. Because the ratios are calculated per unit, selecting items with the highest ratio as much as possible is guaranteed to maximise value.
  3. Reduce the problem to a smaller subproblem: Once an item (whole or part) is selected, the remaining capacity of the knapsack and the list of items reduce, effectively creating a smaller equivalent problem.
  4. Solve the subproblem: Continue choosing items with the maximum value-to-weight ratio until the bag is filled. If the last item cannot fit entirely, take a fraction of it to complete the capacity.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

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

class Solution {
public:
    double fractionalKnapsack(int W, vector<int>& weights, vector<int>& values, int n) {
        vector<pair<double, pair<int, int>>> items;
        
        for (int i = 0; i < n; ++i) {
            items.push_back({(double)values[i] / weights[i], {weights[i], values[i]}});
        }

        // Sort items by value-to-weight ratio in descending order
        sort(items.rbegin(), items.rend());
        
        double max_value = 0;  // total value accumulated
        for (auto item : items) {
            int weight = item.second.first;
            int value = item.second.second;

            if (W >= weight) {
                max_value += value;  // take the full item
                W -= weight;
            } else {
                max_value += item.first * W;  // take the fraction of the item
                break;
            }
        }
        
        return max_value;
    }
};

// Example usage
int main() {
    Solution solution;
    vector<int> weights = {10, 20, 30};
    vector<int> values = {60, 100, 120};
    int capacity = 50;
    cout << "Maximum value: " << solution.fractionalKnapsack(capacity, weights, values, weights.size()) << endl;
    return 0;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

class Solution {
    static class Item {
        double ratio;
        int weight;
        int value;
        
        Item(double ratio, int weight, int value) {
            this.ratio = ratio;
            this.weight = weight;
            this.value = value;
        }
    }
    
    public double fractionalKnapsack(int W, int[] weights, int[] values, int n) {
        List<Item> items = new ArrayList<>();
        
        for (int i = 0; i < n; ++i) {
            items.add(new Item((double) values[i] / weights[i], weights[i], values[i]));
        }

        // Sort items by value-to-weight ratio in descending order
        items.sort((a, b) -> Double.compare(b.ratio, a.ratio));
        
        double max_value = 0;  // total value accumulated
        for (Item item : items) {
            if (W >= item.weight) {
                max_value += item.value;  // take the full item
                W -= item.weight;
            } else {
                max_value += item.ratio * W;  // take the fraction of the item
                break;
            }
        }
        
        return max_value;
    }
    
    // Example usage
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] weights = {10, 20, 30};
        int[] values = {60, 100, 120};
        int capacity = 50;
        System.out.println("Maximum value: " + solution.fractionalKnapsack(capacity, weights, values, weights.length));
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution:
    def fractionalKnapsack(self, W, weights, values, n):
        items = []
        for i in range(n):
            items.append((values[i]/weights[i], weights[i], values[i]))
        
        # Sort items by value-to-weight ratio in descending order
        items.sort(reverse=True, key=lambda x: x[0]) 
        
        max_value = 0  # total value accumulated
        for ratio, weight, value in items:
            if W >= weight:
                max_value += value  # take the full item
                W -= weight
            else:
                max_value += ratio * W  # take the fraction of the item
                break
        
        return max_value

# Example usage:
solution = Solution()
weights = [10, 20, 30]
values = [60, 100, 120]
capacity = 50
print("Maximum value:", solution.fractionalKnapsack(capacity, weights, values, len(weights)))

Complexity

  • ⏰ Time complexity: O(n log n). Sorting items by their v[i]/w[i] ratio takes O(n log n). Filling the knapsack only takes O(n).
  • 🧺 Space complexity: O(n). To store the value-to-weight ratios and sorting, we use additional space proportional to the number of items.