Fractional Knapsack

Problem Solved

In this section we will describe the greedy algorithm to solve the Fractional Knapsack problem.

Design and Strategy

Recall that in an instance of the fractional knapsack problem, each item has a value \(v_i\) and weight \(w_i\), the knapsack has a capacity \(W\), and items may be taken in arbitrary fractions. The objective is to maximize total value subject to the weight limit. It turns out that this problem yields easily to a greedy algorithm based on a simple rule: An object with a higher value-to-weight ratio (also called value density) is a better use of space than one with a lower ratio. This leads to the following algorithm.

High-Level Algorithm

1. Compute each item's value density \(r_i = v_i / w_i\)
2. Sort items by \(r_i\) in descending order.
3. Initialize totalValue = 0 and remaining = W.
4. Scan items in order (descending by value density):
   1. If an item fits entirely, take it; update totalValue and remaining.
   2. Otherwise, take the fraction that fits and stop (capacity is now full).

This greedy approach provides an optimal solution to the fractional knapsack problem because the contribution of each item grows linearly with how much of it is taken. Every unit of weight from an item with a higher value density yields more benefit than a unit from a lower-density item. Thus, filling the knapsack by always taking as much as possible of the remaining highest-density item must lead to the maximum total value.

Pseudocode

Here is a more detailed version of the algorithm that processes items in order of decreasing value density while keeping track of the total value collected and the remaining capacity.

1. For each item \(i\), compute \(r_i = v_i / w_i\).
2. Sort items by \(r_i\) in descending order.
3. Set \( \text{totalValue} = 0 \) and \( \text{remaining} = W \).
4. For each item \(i\) in sorted order:
   1. If \( \text{remaining} = 0 \), stop.
   2. If \( w_i \le \text{remaining} \):
      • \( \text{totalValue} \gets \text{totalValue} + v_i \)
      • \( \text{remaining} \gets \text{remaining} - w_i \)
   3. Else (only a fraction fits):
      • Let \( f = \text{remaining} / w_i \).
      • \( \text{totalValue} \gets \text{totalValue} + f \cdot v_i \)
      • \( \text{remaining} \gets 0 \) and stop.
5. Return \( \text{totalValue} \).

More work is needed to extract the items and amounts to take, but we leave that to the reader.

Note: This greedy approach is only optimal for the fractional knapsack problem and not the 0-1 Knapsack Problem where items cannot be split. The greedy approach will sometimes yeild suboptimal solutions in that case. If you have not yet encountered that variant, you will soon—it provides a valuable contrast to the fractional case.

Implementation in Java, C++, Python

The core idea is the same in all three implementations: compute the value-to-weight ratio for each item, sort the items by that ratio in decreasing order, and then take as much as possible of each item until the knapsack is full. Each version maintains a running total of value and the remaining capacity. These implementations assume all item weights are strictly positive; handling zero-weight or zero-value items would require a few extra checks but does not change the main greedy idea. In every language, built-in sorting functions are used to keep the focus on the algorithm rather than the mechanics of sorting.

• Java: Each item is represented by a simple Item class that stores its value and weight and defines how items compare to one another. By implementing Comparable<Item>, each object can order itself relative to others based on its value-to-weight ratio. The compareTo method uses Double.compare(r2, r1) to sort items in descending order, so higher-value-per-weight items appear first when calling Arrays.sort(items).
• C++: The function compare() defines how two Item objects are ordered—by comparing their value-to-weight ratios. The standard library function sort() takes three arguments: the beginning of the array (items), the position just past the end (items + n), and the comparison function to use (compare). This sorts the array of items in decreasing order of ratio before the greedy filling step.
• Python: In Python, items are represented as pairs (value, weight). A small helper function ratio() computes each item’s value-to-weight ratio, which is used as the sorting key. The built-in sort() method then orders the list in decreasing ratio before the greedy filling loop.

class Item implements Comparable {
  int value, weight;
  Item(int v, int w) { value = v; weight = w; }

  @Override
  public int compareTo(Item other) {
    double r1 = (double) value / weight;
    double r2 = (double) other.value / other.weight;
    return Double.compare(r2, r1); // descending
  }
}

double fractionalKnapsack(Item[] items, int capacity) {
  // Sort by value-to-weight ratio (descending).
  Arrays.sort(items);

  double total = 0.0;
  for (Item it : items) {
    if (capacity == 0) break;
    if (it.weight <= capacity) {
      capacity -= it.weight;
      total += it.value;
    } else {
      total += it.value * (capacity / (double) it.weight);
      capacity = 0;
    }
  }
  return total;
}

#include <algorithm>

struct Item {
  int value, weight;
};

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

double fractionalKnapsack(Item items[], int n, int capacity) {
  std::sort(items, items+n, compare);
  double total = 0.0;
  for (int i = 0; i < n; i++) {
    if (capacity >= items[i].weight) {
      capacity -= items[i].weight;
      total += items[i].value;
    } else {
      total += items[i].value * ((double)capacity / items[i].weight);
      break;
    }
  }
  return total;
}

def fractional_knapsack(items, capacity):
    # Helper function to compute value-to-weight ratio
    def ratio(item):
        value, weight = item
        return value / weight

    # Sort by ratio in decreasing order
    items.sort(key=ratio, reverse=True)

    total = 0.0
    for value, weight in items:
        if capacity == 0:
            break
        if weight <= capacity:
            capacity -= weight
            total += value
        else:
            total += value * (capacity / weight)
            capacity = 0
    return total

These implementations are intentionally simple to put the focus on the greedy structure. In practice, you might also return which items (and what fraction) were taken, and/or precompute ratios to avoid repeated division in the sort key. Neither change affects the time complexity, but will affect the constants.

Time/Space Analysis

Time Complexity: Sorting the \(n\) items by their value-to-weight ratio takes \(O(n \log n)\), and the subsequent greedy scan runs in \(O(n)\). The overall time complexity is therefore \(O(n \log n)\).

Space Complexity: As presented above, the algorithm requires only \(O(1)\) additional space if sorting is performed in place. Explicitly storing the value-to-weight ratios would require \(O(n)\) space, and implementing the algorithm to return the list of selected items (and fractions) would also use up to \(O(n)\) additional space.

Variations and Improvements

• 0-1 Knapsack (contrast): When each item must be taken whole, the density rule is not optimal. The greedy algorithm can serve as a fast heuristic to obtain approximate solutions, but it will sometimes be suboptimal. Exact solutions typically use dynamic programming or branch-and-bound.
• Unbounded (Repeated Items Allowed): When fractional amounts are permitted, allowing repeated items adds no new complexity—the same density-based greedy rule still produces an optimal solution. If items must be taken whole (i.e. an unbounded version of the 0-1 knapsack problem), the greedy method is still not guaranteed to be optimal.
• Avoiding Full Sort: Instead of completely sorting all \(n\) items by ratio, it is possible to use a linear-time selection or partition algorithm to find the "cutoff" item—the one that would be partially taken. All items with higher ratios are taken fully, and the cutoff item is taken in part. This approach runs in \(O(n)\) expected time (and \(O(n)\) worst case using the median-of-medians method, although the overhead of this is almost certainly not worth it).
• Ties and Stability: Items with equal value-to-weight ratios can be taken in any order without affecting the total value. If you care which one becomes the partial item, you can break ties using another criterion—such as smaller weight, larger value, or original input order. These choices do not change the optimal total but may affect which item is taken fractionally.
• Numerical Robustness: Comparing value-to-weight ratios directly using division can introduce rounding errors with floating-point arithmetic. Instead of testing whether \(v_1 / w_1 > v_2 / w_2\), multiply both sides by the positive denominators and compare integer products: \(v_1 \cdot w_2 > v_2 \cdot w_1\). This cross-multiplication avoids division entirely and yields the same ordering without precision loss.
• Returning the Solution: If we also want to know which items (and what fractions) are taken, the algorithm must record that information while filling the knapsack. Storing these selections requires up to \(O(n)\) additional space but provides a complete description of the optimal solution.

Links to Resources

• Wikipedia: Knapsack problem Overview of variants (including fractional) and standard algorithms.
• GeeksforGeeks: Fractional Knapsack Step-by-step greedy solution with code and dry run.
• Hello Algo: Fractional knapsack Concise explanation, figures, and why greedy is optimal.
• NIST DADS: Fractional knapsack Short definitional entry from NIST's algorithm dictionary.

Reading Comprehension Questions

1. Greedy Choice: What is the key idea behind the greedy rule for the fractional knapsack problem?
2. Order of Processing: Why does the algorithm sort items by value-to-weight ratio before filling the knapsack?
3. Partial Items: How does the algorithm handle the first item that does not fit entirely?
4. Optimality: Why is the greedy method guaranteed to produce an optimal solution for the fractional case but not for the 0-1 case?
5. Algorithm Trace: In the worked example, which item is taken only partially, and why does the algorithm stop afterward?
6. Complexity: What are the time and space complexities of the algorithm, and which step dominates the running time?
7. Extensions: How could you modify the algorithm if you also wanted to know which items (and what fractions) were chosen?

In-Class Activities

1. Return the Chosen Items: Modify the pseudocode so it also returns a list of items (and fractions) taken. Verify your algorithm with the worked example on the page (and/or one from the demo).
2. Greedy on 0-1 Knapsack: Create an instance of the 0-1 Knapsack problem whose optimal solution cannot be obtained from the greedy algorithm. Explain why the algorithm fails.
3. Bounded Variant: Suppose each item has a limited number of copies. How would you modify the algorithm if fractional amounts are still allowed? What if they are not?
4. Fractional versus 0-1 Knapsack: Choose a few small datasets that can be used for both the fractional and 0-1 knapsack problems. Compute the optimal solution for each dataset under both interpretations. Compare the resulting total values. Do you notice a pattern? What does this suggest about how the optimal fractional solution relates to the optimal 0-1 solution on the same data?
5. Which Seems Easier? Between the fractional and 0-1 versions of the knapsack, which problem feels easier to solve, and why? Defend your intuition. Then have a discussion about what the actual answer is. Your instructor may need to help with this, especially if you haven't discussed the dynamic programming algorithm for 0-1 knapsack problem yet.

Homework Problems

1. Full Trace (7 items): Given items (value, weight) = [(24,4), (18,3), (20,10), (10,2), (12,6), (30,15), (25,5)] and capacity \(W = 20\):
   1. Compute each item's value-to-weight ratio and sort in decreasing order.
   2. Trace the greedy algorithm step by step, showing remaining capacity, fraction taken (if partial), and running total value.
   3. Report the final total value.
2. Counterexample (0-1 Knapsack): Construct a small 0-1 knapsack instance (5-7 items) where sorting by ratio and taking greedily is not optimal. Provide:
   1. The item list and capacity,
   2. The greedy order and its total value,
   3. The optimal 0-1 subset and its total value,
   4. A brief explanation of why the greedy choice fails here.
3. Implementation and Output: Implement the fractional knapsack algorithm in a language of your choice. Run it on [(70,10), (100,20), (120,30), (65,13), (40,8)] with \(W=35\). Output both the maximum value and the list of chosen items with fractions taken (e.g., \((\text{item}, \text{fraction})\)). (Note: multiple items have the same ratio; the total value should be the same even if a different item becomes partial.)
4. Ties and Stability: Create an input with at least three items sharing the same value-to-weight ratio but different weights. Apply the greedy algorithm under two different tie-breakers (e.g., smaller weight first vs. original input order). In each case, show which item becomes partial and confirm that the final total value is unchanged.
5. Numerical Robustness: Write a comparator/key function that orders items by ratio without using division—compare \(\,v_1/w_1\) and \(\,v_2/w_2\) by checking \(v_1\cdot w_2\) vs. \(v_2\cdot w_1\). comparing using both methods to sort the items in [(1000003, 2000006), (500001, 1000000), (7,14), (9,18)]. List the resulting order and briefly justify what benefits cross-multiplication has.
6. Unbounded (Repeated Items Allowed): Solve the fractional knapsack problem where you can take an unlimited number of copies of each item. Give a clear pseudocode of your algorithm and analyze its time complexity.
7. Greedy for Time Allocation: Suppose you have \(n\) independent projects, each offering a value rate \(r_i\) (dollars per hour) up to a maximum of \(t_i\) hours. You have at most \(T\) total hours to spend. Design a greedy algorithm to maximize the total value earned. Give the computational complexity of your algorithm.
8. Greedy Coin Change: You want to make a target amount using the fewest whole coins. A natural greedy rule is to always take as many of the largest denomination as possible, then move to the next smaller one.
   1. Apply this algorithm to U.S. coin denominations (1¢, 5¢, 10¢, 25¢) to make 63¢. Does it give the optimal solution?
   2. Try it for a few other values. Does the greedy approach always work for U.S. coin denominations? Justify your answer.
   3. Now design your own coin system where the same greedy rule sometimes fails to find the minimum number of coins.
   4. Explain what is structurally different about the two coin systems—why does one always yield to the greedy algorithm while the other does not?