Fractional knapsack and job sequencing

Why it matters

The first lesson showed that a greedy rule is the whole problem. This lesson shows two more problems, and the rule changes each time. In fractional knapsack the rule is a ratio. In job sequencing the rule has two parts: sort by profit, then place each job in a specific slot. Both are common in interviews, and both are short to code once the rule is clear. Both also contain small traps, such as integer division and a slot chosen in the wrong direction, which give wrong answers without any error message. This lesson shows you each trap and how to see it.

Words you will need

• Knapsack: a bag with a weight limit. The name comes from the sack a traveller carries on their back.
• Capacity: the largest total weight the bag can hold.
• Value: how much an item is worth to you. Value is a number you choose, not a weight.
• Weight: how heavy an item is. In these problems weight and value are whole numbers in the input.
• Ratio: one number divided by another. The value per unit of an item is its value divided by its weight. It tells you how much worth each unit of weight carries.
• Fraction: a part of an item. If an item weighs 30 and you take 20 units of it, you have taken two thirds of it.
• Integer division: division of whole numbers, which throws away the part after the decimal point. In C++, 7 / 2 is 3, not 3.5.
• Cast: a conversion that tells C++ to treat a value as another type. (double)a treats a as a decimal number.
• Cross-multiplication: comparing two fractions p/q and r/s by checking p * s against r * q, which avoids division altogether.
• Deadline: the last time slot in which a job may run.
• Slot: one unit of time. In this lesson each job takes one slot, and the slots are numbered 1, 2, 3 and so on.
• Profit: the reward for running a job. It is a number you choose, like a value.
• Floor: the largest whole number that is not more than a value. The floor of 3.7 is 3.

One idea, two problems

In both problems you have a limited resource: weight capacity in one case, time slots in the other. You want to spend it on the items that give the most reward. Greedy works by ranking the items and taking them in order. The question for each problem is what ranking matches what the resource really buys.

For a knapsack, what the bag buys is capacity. So the right ranking is by reward per unit of capacity, which is the value per unit of weight. For a job schedule, what the press buys is time slots. Every job uses exactly one slot, so the right ranking is by profit alone, but the placement of each job depends on its deadline.

Those two sentences are the whole plan. The rest of the lesson is about making them exact, testing them, and avoiding the traps that catch most beginners.

Fractional knapsack: the everyday version

Picture a bin of rice at a shop. You may scoop out any amount, not only whole bags. Your bag holds 50 kilograms. Some rice is worth more per kilogram than other rice. If you fill the bag with the most valuable rice per kilogram first, and then fill the rest with the next best, you get the most value for your bag. You never take a poorer kilo when a better one is still available.

That scooping picture is the fractional version of knapsack. You may take any part of an item. The greedy rule follows from the scooping picture. Take items in order of value per unit of weight, highest first. Take each item whole while it fits. When the next item does not fit whole, take only the amount that still fits, and stop.

The precise version

Give each item a value v and a weight w. Its value per unit is v / w. Sort the items so that the highest value per unit comes first.

Walk down the sorted list with a variable capacity that starts at the bag's limit. For each item:

• If the whole item fits, that is, if its weight is at most capacity, take all of it. Add its value to the total, and subtract its weight from capacity.
• If it does not fit, take the part that fills the bag. Take capacity units of it, and add v * capacity / w to the total, using decimal arithmetic. Then stop, because the bag is full.

The part you take from an item is worth exactly its value per unit times the number of units you take. That is why the formula multiplies the value per unit by the amount taken.

A worked example by hand

Take three items and a capacity of 50. The items are A with value 60 and weight 10, B with value 100 and weight 20, and C with value 120 and weight 30.

Step 1 is the value per unit for each item. A gives 60 divided by 10, which is 6. B gives 100 divided by 20, which is 5. C gives 120 divided by 30, which is 4. The sorted order is A, B, C.

Step 2 walks the list with capacity 50. The table below shows each step.

Step 3 adds the values. 60 plus 100 plus 80 is 240. The part of C is 20 units out of 30, which is two thirds. Two thirds of 120 is 80, so the formula gives the same answer.

A bag of capacity 50 filled with item A, item B and two thirds of item C

The bag is exactly full, and the answer is 240. No other choice does better, because each unit of capacity in the bag is worth at least as much as any unit left out. Lesson 4 turns that sentence into a proof.

Why the ratio, and not the value

It is tempting to sort by value alone, because bigger values look better. Try it on the same three items. Sorted by value, the order is C (120), B (100), A (60). C weighs 30, so it fits whole and leaves 20 units. B weighs 20, so it fits exactly and leaves 0. A does not fit at all. The total is 220.

The ratio rule finds 240. C has the lowest ratio, and it is the item the ratio rule takes only in part. Value alone places C first, and C uses 30 of the 50 units for a ratio of 4. The item A, with ratio 6, would have been better in that spot. Sorting by value alone looks at the reward and ignores the cost of the space it uses. The ratio is the reward per unit of the thing that is scarce.

Integer division: the first trap

Now a trap that catches almost every beginner. Suppose you compute the ratio like this:

(a.value / a.weight) > (b.value / b.weight)

If value and weight are both int, then / is integer division. Item A with value 100 and weight 30 gives 100 / 30, which is 3, not 3.33. Item B with value 60 and weight 20 gives 3 as well. The two ratios look equal, so the sort may put them in either order, and the greedy walk can take the wrong one.

The fix is to make one operand a decimal number before the division. The cast (double)a.value / a.weight converts a.value to double first, so the division becomes decimal division. The cast must come before the division. Writing (double)(a.value / a.weight) does the division in integers first, then converts a value that has already lost its fraction. That is the same mistake in a different place.

The first program below makes both errors visible with real numbers.

Program 1: the integer division trap

This program needs no input. Click Run and read the output.

The output you should see:

integer ratios: 3 and 3
double ratios:  3.33333 and 3
cast too late:  3

With integer division, A and B look tied at 3. With the cast in front, A is 3.33 and B is exactly 3, so A should come first. The third line shows that a cast placed after the division does nothing useful, because the fraction was already gone.

A detail of the output: cout shows at most six significant digits by default, so 3.333333 appears as 3.33333. This is only about display. The comparison inside the program uses the full value.

Program 2: fractional knapsack in C++

Type the input below into the Input box, then press Run. The first line holds the item count and the capacity. Each of the next lines holds one item, with its value first and its weight second.

3 50
60 10
100 20
120 30

The output you should see:

take 10 units of an item worth 60
take 20 units of an item worth 100
take 20 units of an item worth 120
total value 240.00

Walk through the key lines. The comparator a.value * b.weight > b.value * a.weight is cross-multiplication. For items with value and weight a and b, the ratio a.value / a.weight is bigger than b.value / b.weight exactly when a.value * b.weight is bigger than b.value * a.weight. Both sides are whole numbers, so no division and no rounding are involved. For the input here, the largest product is 120 times 20, which is far from the limit of an int. The rule for large inputs is in the Common mistakes section.

The line int take = min(capacity, it.weight); decides how much of the item to take. It is the whole weight if the item fits, and the leftover capacity otherwise. The next line adds the value of that amount. (double)it.value * take / it.weight first turns the value into a double, then multiplies by the amount taken, then divides by the full weight. Each step keeps the fraction, which is what the scoop needs.

The break at the start of the loop stops the walk once the bag is full. Without it, the loop would keep looking at items that take nothing, which is harmless but wasteful.

The line with fixed and setprecision(2) prints two digits after the decimal point. It makes the output read 240.00. It needs the <iomanip> header, which Program 2 includes.

Notice that the visualizer below is a selection sort, not the ratio sort. It is included because the same comparison step appears here, and you can watch how the largest remaining value moves to its place one step at a time.

In a selection sort, each pass finds the largest remaining item and swaps it into place. The ratio sort in Program 2 does the same job with a different comparison. Each comparison is a cross-multiplication, but the placement idea is the same.

Why the ratio rule is optimal

Here is the intuition, in words, before the proof in lesson 4. Imagine each unit of capacity as a slot in the bag. Each slot can hold one unit of some item, and each unit of an item earns its value per unit. The greedy walk fills the best slots first. If the bag ever held a unit of a worse item while a better unit was left out, you could swap that unit for the better one and the total would go up or stay the same. So the best answer never leaves a better unit out in favour of a worse one, and the greedy walk is that best answer.

This argument works only because you may take fractions. If you must take whole items, a better unit that is part of a large item may not fit, and the swap fails. That is the 0/1 knapsack, covered at the end of this section and again in lesson 4.

The 0/1 knapsack, briefly

In the 0/1 version each item is all or nothing. You cannot scoop part of it. Use the same three items and capacity 50. The ratio rule takes A and B, which weigh 30 and give 160, then cannot fit C, which weighs 30 but only 20 is left. The total is 160. The best all-or-nothing choice is B and C, which weigh 50 and give 220. The ratio rule loses 60 here.

So the same greedy rule gives 240 when you can scoop, and 160 when you cannot. The rule did not change, but the problem did. Module 26 solves the all-or-nothing version with dynamic programming, and lesson 4 of this module shows the failure in code.

Complexity of fractional knapsack

Sorting costs O(n log n). The walk costs O(n), because each item is visited once. The total is O(n log n). The extra space is O(1) beyond the items, since the walk keeps only the total and the capacity left.

Job sequencing with deadlines

Now the second problem. Each job takes exactly one time slot. Each job has a deadline, which is the last slot in which it may run. Each job also has a profit, which is what you earn when it runs. The press runs at most one job per slot, so you must choose which jobs run and in which slots. The goal is the largest total profit.

Think of a print shop with one press. Some print jobs must be ready by the morning, and others by the afternoon. Running a job after its deadline earns nothing. The shop wants as much profit as it can get from the day.

The greedy rule has two parts.

1. Sort the jobs by profit, highest first. The most valuable job gets the first chance at a slot.
2. For each job in that order, place it in the latest free slot that is not after its deadline. If there is no free slot at or before the deadline, skip the job.

The second part is the one people get wrong. Why the latest free slot and not the earliest? Keeping early slots free leaves room for jobs with tight deadlines, which can only use early slots. Using an early slot for a job that could have used a late slot can block a tight job later.

Why latest, not earliest

Take two jobs. Job X has deadline 2 and profit 50. Job Y has deadline 1 and profit 40.

Suppose you put X in the earliest free slot. The earliest free slot is slot 1. Now Y has deadline 1, so it needs slot 1, which is taken. Y is skipped. The total is 50.

Suppose you put X in the latest free slot that is at most its deadline. That is slot 2. Y needs slot 1, which is free, so Y runs. The total is 90.

The latest-slot rule keeps slot 1 free for the job that needs it. The earliest-slot rule wastes it on a job that had another choice. That is the whole reason for "latest".

Worked example by hand

Take five jobs: a with deadline 2 and profit 100, b with deadline 1 and profit 19, c with deadline 2 and profit 27, d with deadline 1 and profit 25, and e with deadline 3 and profit 15. There are five slots, numbered 1 to 5, but only jobs with deadlines up to 3 can use them.

Step 1 sorts by profit, highest first: a (100), c (27), d (25), b (19), e (15).

Step 2 places each job. The table below tracks the slots, using a dash for a free slot.

Step 3 adds the profits of the placed jobs. a, c and e give 100 plus 27 plus 15, which is 142. Jobs d and b were skipped, because the only slot they could use was taken by c, which had a higher profit.

Slot table after placing the five jobs, with c in slot 1, a in slot 2 and e in slot 3

The diagram shows the final slots. Slots 4 and 5 stay free because no job has a deadline that reaches them and still fits. A free slot does not reduce the answer.

Program 3: job sequencing in C++

Type the five jobs below into the Input box, then press Run. The first line holds the job count. Each next line holds a job name, its deadline, and its profit.

5
a 2 100
b 1 19
c 2 27
d 1 25
e 3 15

The output you should see:

slots: cae--
profit 142

The slot string has five characters because the program keeps one slot for each job. Slots 4 and 5 show as dashes because nothing filled them. The answer 142 matches the hand calculation.

Look at the inner loop. It starts at min(n, j.deadline) and counts down. The min matters. A deadline can be bigger than the number of jobs, such as 1000 when there are 5 jobs. No more than n jobs can run, so slots after n are never needed, and the min keeps the loop inside the array. The loop stops at the first free slot it finds, and break leaves the loop at once.

The char type stores one letter, which is the job name. plan += slot[t] adds one character to the string. A string starts empty, so plan ends as the five slots joined together.

Program 4: tracing the placements

As in lesson 1, a trace shows every decision. This version prints each job, the slot it gets, and the state of all the slots after each step. Use the same five-job input as Program 3.

5
a 2 100
b 1 19
c 2 27
d 1 25
e 3 15

The output you should see:

job a (deadline 2, profit 100): slot 2
   slots now: -a---
job c (deadline 2, profit 27): slot 1
   slots now: ca---
job d (deadline 1, profit 25): no free slot, skipped
   slots now: ca---
job b (deadline 1, profit 19): no free slot, skipped
   slots now: ca---
job e (deadline 3, profit 15): slot 3
   slots now: cae--

Read the second and third blocks together. When c arrives with deadline 2, slot 2 is taken by a, so the search moves to slot 1, which is free. Later, d and b both need slot 1, which is now taken, and they are skipped. The trace makes clear that the skips are the rule working, not a bug.

Complexity of job sequencing

Sorting costs O(n log n). The placement loop may look at up to n slots for each job, which makes the simple version O(n squared) in the worst case. For the sizes in an interview, that is fine, and it is easy to explain. The faster version uses a disjoint-set structure, often called union-find, which remembers the latest free slot at or before each deadline. With it, each placement is nearly constant time, and the total is O(n log n) for the sort plus almost-linear time for the placements. Describe the faster version if the interviewer asks for it, and write the simple one unless you are asked for more.

What happens inside the computer

Each Job holds a char and two int values, which is about 12 bytes. The vector<Job> stores them side by side in one block. The sort rearranges that block. The slot vector is a separate small block of char values, one byte per slot, so the slot table costs little memory.

When the inner loop writes slot[t] = j.id, the computer changes one byte in that block. When it reads slot[t] == '-', it compares that byte with the dash character. The dash is stored as its code number, so the comparison is a comparison of two small numbers. Nothing about the job is copied during the search.

For the fractional knapsack in Program 2, the double variable total holds the running value. A double stores a number with about 15 significant digits, which is far more than these examples need. The take and capacity values stay int, because the amounts taken are whole units.

Checking a fractional answer on paper

You can check any fractional knapsack answer with four quick tests, without rerunning the program.

First, the total weight taken must not be more than the capacity. Add up the units taken from each item. For the example in this lesson, 10 plus 20 plus 20 is 50, which is exactly the capacity.

Second, every item taken whole must be worth its full value, and the one partial item must be worth its share. The share is the units taken divided by the item's weight. Twenty of thirty units is two thirds, and two thirds of 120 is 80.

Third, if the bag still has room at the end, every item must have been taken whole. If there is room left and an item was skipped, the answer is wrong, because a whole item that fits should have been added. The simple walk never leaves room while an item still fits, so this test catches a broken loop.

Fourth, the order must be right. Pick any two items that are next to each other in the sorted list, and compare their ratios by hand. The earlier one must have the same or the higher value per unit. If you find a pair in the wrong order, the sort comparator is wrong.

These four tests take a few minutes and catch most mistakes. They are a good habit in an interview too, because you can say each test out loud while you check the answer.

Common mistakes

Integer division in the ratio. The symptom is an answer that is too small when items are close in ratio, and no error message at all. The fix is the cast before the division, or the cross-multiplication used in Program 2. Program 1 shows the bad output so you can recognise it.

Sorting by value alone. The symptom is an answer of 220 where 240 was expected. The fix is to sort by value per unit of weight.

Placing jobs in the earliest free slot. The symptom is a smaller profit than expected, with a tight-deadline job skipped. The fix is to search from the deadline downward, not from slot 1 upward.

Forgetting the deadline cap. If you write for (int t = j.deadline; ...) without min(n, ...), a deadline of a million makes the array index run far past its end. The program may crash with no clear message, or it may write into memory it does not own. Always cap the deadline at the array size.

Missing <iomanip>. If you print with setprecision and forget the header, g++ stops with this message:

error: ‘setprecision’ was not declared in this scope

The fix is #include <iomanip> at the top. The same kind of message appears for any name that comes from a header you did not include.

Printing the wrong precision. cout << total alone can show 240 or 240.5, depending on the value. If the problem asks for two decimal places, use fixed and setprecision(2) and check the output format exactly, because a judge compares the text.

Debugging walkthrough

Suppose your fractional knapsack prints 220 for the three-item example, when the answer should be 240. Follow these steps.

First, print the ratio of each item after the sort, as a decimal. If the order is A, C, B, the sort is wrong. Check the comparator for a missing cast or a wrong direction of >.

Second, print the amount taken from each item, as Program 2 does. If item C shows 30 units instead of 20, the capacity was not updated correctly, or the min is using the wrong value.

Third, check the arithmetic. The partial value must be value * take / weight, with the cast on the value. A formula value * (take / weight) loses the fraction, because take / weight is integer division and becomes 0 for any take less than weight.

For job sequencing, use the trace in Program 4. Find the first job that gets a different slot from your hand calculation, and check the search loop above it. Most bugs are in the direction of the loop or the cap.

Variations and edge cases

Capacity zero. The loop breaks at once and the answer is 0. The break at the top handles it.

A deadline larger than the number of jobs. The min caps it. Jobs with huge deadlines behave like jobs with deadline n.

Zero profit. A job with profit 0 never helps the total, so the algorithm may place it or skip it. The total is the same either way.

Ties in profit. When two jobs have the same profit, the sort may put either first. The total profit is the same, because either order leads to the same set of usable slots. The slots printed may differ.

Ties in ratio. Two items with the same value per unit give the same total value in any order, because each unit of capacity is worth the same.

All jobs fit. If every job can get a slot, the answer is the sum of all profits.

Item weights of zero. The formula divides by the weight, so a weight of 0 is not allowed. The problem statement should say weights are at least 1.

Interview questions you will hear

For fractional knapsack, the usual question is what changes if you cannot take fractions. The answer is that greedy fails, and you should say so and name dynamic programming. For job sequencing, the question is often why the latest slot is right. Use the earliest-slot counterexample from this lesson. A third common question asks for the complexity. Say that the sort dominates, and mention the disjoint-set speedup if you know it.

Practice

1. Easy. Partial fill. With capacity 10 and the three items from the worked example, what is the answer for fractional knapsack?

2. Easy. Compare ratios. Which item has the higher value per unit: (10, 4) or (9, 3)? Give each value as value and weight.

3. Easy. One slot. Five jobs all have deadline 1, with profits 4, 9, 2, 7 and 5. What is the maximum profit?

4. Medium. Find the bug. A student writes double r = a.value / a.weight; to compute the ratio, and sorts by r. Explain what goes wrong and fix it.

5. Medium. The 0/1 answer. Using the same three items and capacity 50, what is the best all-or-nothing value? Show your choice.

6. Medium. Print the rates. Change Program 2 so it prints each item's value per unit before its take line, with two decimal places.

cout << fixed << setprecision(2) << "rate " << (double)it.value / it.weight << "\n";

7. Medium. Trace the slots. Jobs: p deadline 2 profit 10, q deadline 2 profit 20, r deadline 1 profit 5. Give the slots and the total.

8. Medium. Earliest versus latest. Jobs X (deadline 3, profit 60), Y (deadline 1, profit 50), Z (deadline 3, profit 40). Show that placing each job in the earliest free slot gives a smaller total than the latest-slot rule.

9. Hard. Keep the earliest rule honest. Describe a small input where the earliest-free-slot rule and the latest-free-slot rule give the same total. Then describe one where they differ.

10. Hard. Explain the greedy in words. Explain in four sentences why taking the highest value per unit first is best for fractional knapsack, without using the word optimal.

11. Hard. A faster slot search. The simple search loops down from the deadline. Describe how a disjoint-set structure can find the latest free slot at or before a deadline without looping.

12. Hard. Print the slot for each job name. Change Program 3 so it prints, in alphabetical order, the slot each job ran in, or none if it was skipped.

What you now know

• Fractional knapsack sorts by value per unit of weight, takes items whole while they fit, and takes a fraction of the first item that does not fit.
• Sorting by value alone, or dividing integers before the cast, gives a wrong answer without a warning.
• Job sequencing sorts by profit, then places each job in the latest free slot at or before its deadline, and skips it if none is free.
• The latest free slot keeps early slots available for jobs with tight deadlines.
• Both greedy rules are optimal when you may take fractions or when each job takes one slot, but the 0/1 knapsack breaks the first rule.
• Both solutions run in O(n log n) time, dominated by the sort.
• A trace that prints each decision finds placement bugs quickly.