Fractional Knapsack

A thief with a 50 kg bag finds gold dust, silver dust and spices. When you can take any fraction of anything, the best plan is beautifully simple: most valuable kilogram first.

★ Lecture: DP_knapsack · Zaza Gamezardashvili▶ video intermediate⏱ 10 min read

←Builds on

7The Greedy Idea & When It FailsTaking the best value per kilogram first is the greedy choice, and here it is provably safe.2Comparators & StabilityItems are sorted by value per weight with a custom comparator.

Leads to→

100-1 KnapsackWhen items cannot be split the ratio greedy fails, and a table is needed.

1Learn 2Watch 3Play 4Check 5Practice

Learn

The idea, the mechanics and the cost.

01The knapsack problem

The lecture states it like this: there are N items, item i has weight wᵢ > 0 and value pᵢ > 0. Choose a subset whose total weight does not exceed the knapsack capacity W and whose total value is maximal.

In general this problem is NP-complete: no polynomial algorithm for it is known. For small inputs dynamic programming solves it, and that is the second half of the lecture (stage 10).

Our running example is the lecture's: three items of 10, 20 and 30 kg worth $60, $100 and $120, and a knapsack of capacity 50. All three together weigh 60, so something has to stay behind.

02Six variants of one problem

The lecture lists the variants before solving anything, because the rules about how much of an item you may take decide which algorithm works:

Fractional (continuous): any part of any item, and the part keeps its proportional value.
0-1: each item exists once; take it whole or leave it.
Bounded: item i at most kᵢ times.
Unbounded: any number of copies.
Multiple-choice: items are split into groups, one item per group.
Multiple knapsacks: several bags, each with its own capacity.

Only the fractional one gives in to a greedy algorithm. All the others need dynamic programming or worse.

03Fractional: most valuable kilogram first

Compute each item's value per unit of weight: 60/10 = 6, 100/20 = 5, 120/30 = 4 dollars per kg. Since any part can be taken, a kilogram is a kilogram, and you obviously want the most expensive kilograms.

So: put item 1 in whole (10 kg, $60), then item 2 whole (30 kg used, $160). Item 3 no longer fits, so take two thirds of it: 20 kg worth $80. The bag is exactly full and the value is $240.

Why this is optimal: if a solution carried some kilogram of a cheaper item while a pricier kilogram stayed outside, swapping them would raise the value. So the best solution never leaves a better kilogram behind, which is exactly what the greedy builds.

04Forbid splitting and greedy breaks

Same items, but now the 0-1 rule: no fractions. The greedy "best value per kg first" puts in item 1 (it is the most valuable per kg), then item 2, and item 3 does not fit. Result: $160.

But items 2 and 3 together weigh exactly 50 and are worth $220. The greedy lost because it judged items by density, and the leftover space it created (20 kg) could not be filled with a whole item.

With fractions, leftover space is never wasted, which is why the same rule is optimal there. Without fractions you have to compare combinations, and that is the job of the 0-1 knapsack table in stage 10.

Each bar is a 50 kg knapsack; the last row is the fractional answer.

05The algorithm and the lecture's code

From the lecture: sort the items by value per unit of weight, non-increasing, and take them in that order until the knapsack is full. Only the last item may have to be taken partly. If the items together weigh at least W, the knapsack always ends up exactly full.

The lecture's C++ stores each item as a pair<double,double> of (value, weight), sorts with a comparator a.first/a.second > b.first/b.second, and then loops:

if items[i].second <= capacity: take it whole, capacity -= weight, mx += value;
else: mx += value / weight * capacity, capacity = 0, and stop.

The sort costs O(n log n), the loop O(n). Use double (or exact fractions) because the answer need not be an integer.

The lecture's C++C++

Slide 6: comp_item sorts the items by value per unit of weight (first is the value, second the weight), then the loop takes whole items until the last one fits only in part.

#include <bits/stdc++.h>
using namespace std;
typedef pair<double, double> item;
bool comp_item(item& a, item& b){
    return a.first/a.second > b.first/b.second;
}
double mx_profit(item items[], int n, double capacity){
    double mx= 0;
    sort(items, items+n, comp_item);
    for(int i= 0; i<n; i++){
        if(items[i].second <= capacity){
            capacity -= items[i].second; mx+= items[i].first;
        }
        else{
            mx+= items[i].first/items[i].second * capacity;
            capacity= 0; break;
        }
    }
    return mx;
}
int main( ) {
    int n;   item items[100];  double capacity;
    cin>>n>>capacity;
    for(int i=0; i<n; i++){
        cin>>items[i].first>>items[i].second;
    }
    cout<< mx_profit(items, n, capacity) <<endl;
}

Cost at a glance

Sort by value/weightO(n log n)

Greedy fillO(n)

Extra memoryO(1)

Remember

Fractional knapsack: sort by value per kilogram and fill greedily; only the last item is split.
It is optimal because a cheaper kilogram inside and a pricier one outside could always be swapped for profit.
In the 0-1 version the same rule fails ($160 vs $220), so that variant needs dynamic programming.

Watch

The lecture as a narrated explainer video.

▶

Watch the lecture, animated

The video follows the lecture slide by slide: the same example, the same notation. Use it before or after playing with the visualizer.

▶ Open the video page ▣ Open as presentation

Play

Step through the algorithm, then try it on your own input.

👀 What to watch: Watch the $/kg line on each item: the bag fills in that order, and only the last item turns into a percentage.

Interactive visualizerfocus here, then space ← →

Fractional knapsack (greedy)

#1 · 10kg / $60
6.0 $/kg#2 · 20kg / $100
5.0 $/kg#3 · 30kg / $120
4.0 $/kg

capacity 50kg · total value: $0

Fill a knapsack of capacity 50kg to maximize value. Items can be split into fractions. This is the version from the lecture.

Pseudocode

 1 each item has weight w and value p 2 sort items by value/weight ratio, descending 3 take whole items greedily while they fit 4 the last item may be taken as a FRACTION to fill exactly 5 // optimal because items are divisible

1 / 1

Check

Three questions. Pick an answer to see why.

Items (weight, value): A (5, $50), B (10, $60), C (20, $140). Capacity 20, fractions allowed. Best value?

Why does "best value per kg first" fail for the 0-1 knapsack?

You may take each item any number of times (whole copies only). Which variant is this?

Practice

Real problems to lock it in, easiest first.

LeetCodeMaximum Units on a Truck beginner↗LeetCodeMaximum Bags With Full Capacity of Rocks intermediate↗LeetCodeMaximum Price to Fill a Bag intermediate↗CSESBook Shop (0-1 knapsack, needs DP) intermediate↗