Fractional knapsack and job sequencing in Python

Why this lesson matters

These two problems appear in almost every algorithm course and in many interview lists. Each one is solved with a sort and one pass, and the whole puzzle is choosing the right sort key. Get the key right and the greedy loop is short and safe. Get it wrong and the program prints a plausible number that is too small.

By the end of this lesson you will be able to explain why the fractional knapsack sorts by value per unit of weight, solve it in Python with decimal numbers, schedule jobs with deadlines to maximise profit, and recognise the integer division trap that catches most beginners in these problems.

The first principle: a limited budget of something

Both problems share one idea. You have a limited budget of something, and you want to spend it to get the most value. In the knapsack problem the budget is weight, the space in a bag. In the job problem the budget is time, the hours in a day. In each case, some choices use more of the budget than others, and the best choice is the one that gets the most value for each unit of budget spent.

That phrase, value for each unit of budget, is the key to greedy thinking here. Greedy works best when every unit of budget can be judged on its own. If you can compare two options by the value they give per unit, you can rank them, and a single pass can use that ranking.

An everyday analogy

Imagine you are packing a small bag for a trip, and the airline allows only 5 kilograms. You have a jar of spice, a bag of rice and a pack of tea. Each one has a value to you, for example how much you would miss it. Each one has a weight. You want the most value inside 5 kilograms.

A sensible traveller does not ask which item has the biggest value. A large heavy item might use up the whole allowance for little gain. The traveller asks: how much value do I get per kilogram? The spice may be worth a lot for its weight. The rice may be worth less for each kilogram. The traveller fills the bag starting with the best value per kilogram, and if the next item does not fit whole, takes as much of it as still fits.

That second part is what makes this problem different from a yes-or-no packing problem. In the fractional knapsack, you may take part of an item. Think of scooping rice from a sack: you can take 2.5 kilograms, not only whole sacks. Because parts are allowed, there is never a wasted gap in the bag, and the greedy rule is provably best.

Fractional knapsack, defined

Here are the terms, in plain words.

• Capacity is the total weight the bag can hold.
• Each item has a value (how much you gain by taking all of it) and a weight (how much space it uses).
• Value per unit of weight is the value divided by the weight. Call it the ratio. An item worth 60 that weighs 10 has a ratio of 6, which means 6 value for each unit of weight.
• A fraction of an item is a part of it. If you take half of an item, you get half its weight and half its value.

The goal is to choose how much of each item to take, so that the total weight is at most the capacity and the total value is as large as possible.

The rule: sort by value per unit of weight

The greedy rule is short. Sort the items by ratio, highest first. Walk through the sorted list. Take each item whole while it fits. For the first item that does not fit, take the part that fills the rest of the bag, and stop.

Why does this work? Look at what each unit of capacity does. Every unit of weight in the bag holds some value. If you swap a unit that holds a lower ratio for a unit that holds a higher ratio, the total value goes up or stays the same. So the best bag always uses the highest-ratio material first. The exchange argument that proves this is in lesson 4. For now, trust the intuition and check it with a small example.

Here is the algorithm in steps.

1. For each item, compute its ratio, value divided by weight.
2. Sort the items by ratio, from highest to lowest.
3. Set the remaining capacity to the full capacity, and the total value to 0.
4. For each item in order, take the smaller of the item's weight and the remaining capacity. Add the matching part of the value to the total. Subtract the taken weight from the remaining capacity.
5. Stop when the remaining capacity is 0 or the items run out.

Worked example 1: three items, step by step

Here are three items and a bag with capacity 50. Each item is written as value and weight.

Sorted by ratio, from highest to lowest, the order is item 1 (ratio 6), item 2 (ratio 5), item 3 (ratio 4). Now fill the bag.

Item 3 weighs 30, but only 20 units of space are left. So you take 20 of its 30 units, which is two thirds of it. Its value is two thirds of 120, which is 80. The total is 60 + 100 + 80 = 240. The bag is full, and the loop stops.

Compare that with what a beginner might do. Sorting by value alone gives item 3 first, which weighs 30 and leaves 20 units, then item 2, which fits exactly. That gives 120 + 100 = 220. Sorting by weight alone gives item 1 and item 2 first, which is 160, and then item 3 as a fraction, which is 80 more. That also totals 240 in this example, which is a coincidence of these numbers. Only the ratio key is safe for every input.

Decimal numbers in Python

The fraction in step 3 is not a whole number. The value 80 came from 120 times 20 divided by 30, which divides exactly here, but in general it does not. So the total must be a decimal number. In Python, a decimal number is a float.

Python has two division operators. / always gives a float, even when both numbers are whole. // is floor division. It gives the whole part of the answer, rounded down. The program below shows both, and a few cases that surprise beginners.

Output:

floor division, 100 // 30: 3
true division, 100 / 30:   3.3333333333333335
exact fraction:            10/3
floor division, -7 // 2:   -4
0.1 + 0.2 = 0.30000000000000004

The // line gives 3, because the fraction is dropped. That is the trap for this topic. If a ratio is computed with //, items with close ratios are sorted in the wrong order. Use / for every ratio and every fraction of an item.

The line -7 // 2 gives -4, not -3. Floor division rounds toward negative infinity, so the answer goes down. The programs in this lesson use positive numbers only, so this does not affect them, but it is a rule to know.

Floats are approximate. The line 0.1 + 0.2 shows this. Each float holds the closest value the computer can store, and that is not always exact. The programs here are small enough that floats are fine. If you need exact results, the fractions module stores a number as a numerator and a denominator. Fraction(100, 30) prints 10/3 and is exact.

Python does not check the type of a variable when you store a value in it. The statement count: int = 100 / 30 runs, and count holds a float. The : int part is a type hint. It is checked by tools such as mypy, not by the interpreter. The error appears later, when the program uses the value as a whole number:

print(range(100 / 30))

TypeError: 'float' object cannot be interpreted as an integer

A list index must also be a whole number. This line uses a float as an index:

parent = [0, 1, 2, 3]
print(parent[100 / 50])

TypeError: list indices must be integers or slices, not float

The fix is to keep the value a whole number with // where you need a count, and to keep it a float with / where you need a ratio.

The fractional knapsack program

The next program puts the steps into a function. The function takes a list of (value, weight) pairs and the capacity. It sorts by ratio, fills the bag, and returns the total value.

Output:

240.00

Read the program in pieces. The key lambda item: item[0] / item[1] divides value by weight for each item, so the sort compares ratios. The argument reverse=True puts the largest ratio first. Leaving it out would sort the lowest ratio first, which is the opposite of what we want.

The loop is the greedy step. min(weight, capacity) picks the smaller of the item's full weight and the space left. That is the whole item if it fits, or the leftover space if it does not. The value added is the item's value times the fraction of the item taken. The line capacity -= take shrinks the space left. When the space reaches 0, the loop stops at the next check.

The last line uses an f-string with :.2f. That means: show a float with exactly two digits after the decimal point. Python always uses a dot for the decimal point, so no locale setting is needed.

Why the ratio is the right key

It helps to see the argument once in plain words, before the formal version in lesson 4. Suppose an optimal bag holds some amount of item B but has room for more of item A, which has a higher ratio. Take a small amount of B out, the same weight as a little of A, and put A in its place. The bag still fits the capacity, because the weights match. The value changes by the ratio of A times the weight swapped, minus the ratio of B times that same weight. Since A's ratio is higher, the change is positive or zero. So the bag was not optimal, or it was already as good as the swap allows.

That is why the greedy rule is safe for the fractional knapsack. The same swap would not work with whole items, because you cannot swap half of an item for half of another and keep the value exact. That is why the 0/1 version is harder, and why lesson 4 shows where greedy breaks.

The next program puts the ratio rule next to two other rules. It uses the same three items, with a bag of capacity 10 this time, so the answers differ. It prints the total you would get if you sorted by value, by weight, or by ratio. The fill function takes a key, so the three rules share one loop.

Output:

by value:  50.0
by weight: 65.0
by ratio:  65.0

Trace the value rule by hand. The most valuable item is worth 50 and weighs 10. It fills the whole bag, so the total is 50, and nothing else fits. The value rule looks sensible, but it wastes the chance to take two cheap, efficient items.

Now the ratio rule. The ratios are 5 for the first item, 6 for the second and 10 for the third. Sorted by ratio, the third item (weight 2) comes first, then the second (weight 5), then the first (weight 10). The bag takes 2, then 5, which fills 7 units. The first item is cut to the last 3 units, which is 3 of 10, so it gives 15. The total is 20 + 30 + 15 = 65. The weight rule gives 65 too, here, which is why this example does not separate the two. The ratio rule is the one that is safe for every input.

Notice that the printed numbers are 50.0 and 65.0, with a decimal point and a zero. Python prints a float that way. The f"{best:.2f}" format in the earlier program is what controls the number of digits.

Job sequencing with deadlines

The second problem looks different, but it is also a greedy problem with a sort key. You have jobs. Each job takes exactly one hour. Hours are numbered 1, 2, 3, and so on. Each job has a deadline, which is the last hour in which it can be done. It also has a profit, which you receive only if the job is done by its deadline. You can do one job per hour. Your goal is to choose the jobs so that the total profit is as large as possible.

Imagine a repair technician with one visit per hour. Some customers pay a lot but need the repair by a tight time. Others pay less but have looser deadlines. The technician must choose which visits to make, and in which hour.

The greedy rule has two steps. First, sort the jobs by profit, highest first. Second, for each job in that order, place it in the latest free hour on or before its deadline. If no free hour exists, skip the job.

Why the latest free hour, and not the earliest? Because an early hour is valuable to a job with a tight deadline. Suppose a job with deadline 3 is placed in hour 1, when hour 3 was free. Later, a job with deadline 1 arrives and finds hour 1 taken. Placing the first job late, in hour 3, would have kept hour 1 open. Taking the latest free hour keeps the early hours available for the jobs that need them.

Why highest profit first? Because profit is what you are trying to maximise. A high-profit job should get its hour before a low-profit job can take it. A low-profit job takes an hour only when no higher-profit job still needs that hour.

Worked example 2: five jobs, step by step

Here are five jobs as deadline and profit.

Sort by profit, highest first: A (100), C (27), D (25), B (19), E (15). Now place each job. The hours are 1, 2 and 3, and all are free at the start.

The total profit is 142. Jobs B (19) and D (25) both have deadline 1, so both need hour 1. Only one job can have that hour. Job C (27) took hour 1, because hour 2 was taken by A and C has more profit than D. D and B were skipped.

Look at the table again. The "latest free hour" column is the only subtle part. For job C, hour 2 was taken by A, so the search moved to hour 1. For job E, deadline 3, the search started at hour 3, which was free. Every search starts at the deadline and moves earlier, one hour at a time, until it finds a free hour or runs out.

Program: scheduling jobs with a free-hour finder

The simplest way to find the latest free hour is to start at the deadline and walk backwards until you find a free hour. That takes time proportional to the number of hours for each job, which is slow when there are many jobs. A better way uses a list, called parent, that remembers where to look next. Each hour points to the next hour to check. When an hour is taken, it points one step earlier. When you look up a free hour, you follow the pointers, and you shorten the path as you go. That shortening is called path halving.

The program below uses this idea. It prints a line for each job, so you can see every decision. The jobs are written into the program as (deadline, profit) pairs.

Output:

profit 100, deadline 2 -> hour 2
profit 27, deadline 2 -> hour 1
profit 25, deadline 1 -> skipped
profit 19, deadline 1 -> skipped
profit 15, deadline 3 -> hour 3
total profit 142

Read the program from top to bottom. The max line finds the largest deadline, so the parent list is big enough. list(range(max_deadline + 1)) makes the list [0, 1, 2, 3] for this input. The sorted call puts the highest profit first, using the same key idea as the knapsack.

The printed lines match the table in worked example 2. The job with profit 100 is listed first, because the sort put it first. For profit 27 the output says "hour 1", because hour 2 was already taken.

Python integers have no fixed size, so the running total cannot overflow. In some languages a total like this needs a wider type, but here an ordinary int is enough.

What happens inside the parent list

The list parent is the important part. Before any job is placed, every hour points to itself. For the input above, the largest deadline is 3, so parent has four entries, one for each hour from 0 to 3. Hour 0 is a sentinel. It means "no hour left", and it always points to itself.

index:   0   1   2   3
parent:  0   1   2   3     start: every hour is free

The program below replays the five jobs in profit order and prints the list after each one.

Output:

start: [0, 1, 2, 3]
job A: hour 2, parent is [0, 1, 1, 3]
job C: hour 1, parent is [0, 0, 1, 3]
job D: skipped, parent is [0, 0, 1, 3]
job B: skipped, parent is [0, 0, 1, 3]
job E: hour 3, parent is [0, 0, 1, 2]

Job A with deadline 2 starts at hour 2. The function latest_free(parent, 2) finds parent[2] == 2, so hour 2 is free. The program sets parent[2] = 1, which means "hour 2 is taken, look at hour 1 next". The table becomes 0 1 1 3.

Next, job C with deadline 2. latest_free(parent, 2) sees parent[2] = 1, which is not 2, so it follows the pointer. Path halving sets parent[2] = parent[parent[2]] = parent[1] = 1, which changes nothing here. The loop moves to hour 1. parent[1] == 1, so hour 1 is free. The program sets parent[1] = 0, and the table becomes 0 0 1 3. Hours 1 and 2 are taken.

Job D with deadline 1 starts at hour 1. parent[1] = 0, so the loop follows the pointer to hour 0. parent[0] == 0, so the function returns 0. A return value of 0 means no hour is free, and the job is skipped. Job B does the same.

Finally, job E with deadline 3. parent[3] == 3, so hour 3 is free. The program sets parent[3] = 2, and the table ends as 0 0 1 2.

The pointers never point forward, so the loop always ends. Path halving means each lookup gets faster as the program runs. For practical sizes, each lookup is almost a constant-time step. This technique is a small version of a data structure called union-find, which is used in several graph algorithms.

Complexity

Let n be the number of jobs and D be the largest deadline.

• The sort: O(n log n).
• The slot scan without the parent list: each job may walk back through up to D hours, so the total is O(n * D). That is fine for small inputs but slow when both numbers are large.
• The parent list: each lookup is almost constant time, so the placement loop is O(n) after the sort. The total is O(n log n), dominated by the sort.
• Extra space: O(D) for the parent list.

If you are asked for an answer without the parent list, the walk-backwards version is correct and easy to explain. Say the simple version first, then mention that a union-find style list reduces the cost.

Worked example 3: deadlines larger than the job count

Deadlines are not always small. A job might say "deadline 1000", but if there are only five jobs, the schedule cannot use more than five hours. This is an important edge case. Take three jobs with deadlines 100, 100 and 1, and profits 10, 20 and 5.

Sorted by profit: 20 (deadline 100), 10 (deadline 100), 5 (deadline 1). The first job takes the latest free hour on or before 100. The largest deadline in the input is 100, so the list has 101 entries, and hour 100 is free. The job takes hour 100. The second job, also deadline 100, takes hour 99. The third job, deadline 1, takes hour 1. Total profit 35.

This works, but the list is sized by the largest deadline, 100, even though there are only three jobs. If one job had deadline one billion, the list would need one billion entries. That needs far more memory than most computers have, and the program would fail or slow down badly. A better program caps every deadline at the number of jobs. A deadline larger than n cannot be used anyway, because at most n jobs can be placed. The next program runs both versions.

Output:

without cap (total, list length): (35, 101)
with cap (total, list length):    (35, 4)

The cap is one line: d = min(deadline, n). The total is the same, 35, but the list has 4 entries instead of 101. With a deadline of one billion, the difference is the difference between a small list and an impossible one.

Variations and edge cases

• Deadline of zero. A job with deadline 0 cannot be done in any hour, because hours start at 1. The latest_free(parent, 0) call returns 0, which means skipped. Check the input format to see whether zero can happen.
• More jobs than hours. If there are ten jobs with deadline 2, at most two can be done. The algorithm places the two most profitable ones and skips the rest.
• Equal profits. The total is the same in any order of ties, but the printed schedule can change. Python's sort keeps tied jobs in input order, so the output is predictable. Decide on a tie-break if the problem asks for a particular schedule.
• Each job takes more than one hour. This is a different problem. The simple greedy rule no longer works, and the case is closer to the 0/1 knapsack in lesson 4.
• A knapsack item with weight zero. The ratio becomes a division by zero. Python raises an error for this, even when both numbers are floats. Check your inputs for zero weight before you divide.

weight = 0
print(10 / weight)

ZeroDivisionError: division by zero

Common mistakes and their real messages

Sorting the knapsack by value alone or by weight alone. The program runs, but the total is smaller on some inputs. The worked example above shows both wrong rules. The fix is to sort by value divided by weight, using / for the division.

Dividing with //. The ratio is cut to a whole number, so items with close ratios get sorted in the wrong order. For 100 // 30 the answer is 3, but 100 / 30 is 3.3333333333333335. Use / for every ratio and every fraction of an item.

Storing a decimal where a whole number is needed. Python accepts the assignment. The error appears later, when the value is used as a count or an index. The messages are the two TypeError lines shown earlier in this lesson. Keep counts and indexes whole, using // or int() where you need them.

Placing a job at its deadline even when the hour is taken. The program then overwrites a job, or double counts a slot, and the profit is too high. Always search backwards from the deadline until you find a free hour, or until you know none is left.

Off-by-one in the hour numbers. Hours start at 1. If your list uses index 0 for hour 1, every answer shifts by one hour. A job with deadline 1 then uses index 0, which the sentinel rule treats as "no hour left". Keep hour numbers and list indexes equal, and use index 0 only as the sentinel.

Using the deadline as an index without a cap. If a deadline is larger than the list, Python raises an error. For a list with four entries:

parent = [0, 1, 2, 3]
print(parent[4])

IndexError: list index out of range

Read the message. The index is 4, and the list has four entries, so valid indexes are 0 to 3. Either the list is too small, or the deadline was not capped. Fix the list size or add min.

Forgetting to sort first. If you place the jobs in input order, a high-profit job may be skipped because a low-profit job took its hour. The fix is to sort by profit, highest first, before placing anything.

Debugging walkthrough: following the parent list

When the job program gives a surprising total, print the parent list after each job. The lists in the worked example are a good model. Here is a short checklist.

1. Print the sorted order of jobs. Check that the highest profit is first.
2. For each job, print the deadline, the hour that latest_free returned, and the new profit. A skipped job should return 0.
3. If a job is placed in an hour that you think is taken, check the line parent[slot] = slot - 1. That line must run after the hour is used.
4. If the total is too high, check whether a job can use the same hour twice. Print the parent list and see whether an entry points to itself after a placement.

The program that prints the list after each job is the most important trace. Read the lines in order. Each one should follow from the table in worked example 2.

Interview questions you should be ready for

1. Why sort the knapsack by ratio, not by value? A high-value item can be heavy and waste capacity. Ratio measures value for each unit of space, which is what the bag needs. Give the 220 versus 240 example with the three items.
2. Why can you take a fraction of an item in the fractional version? Because a fraction keeps the ratio exact. With whole items, the swap argument breaks, and greedy can fail. That is the 0/1 knapsack, covered in lesson 4.
3. Why do jobs get the latest free hour? So that early hours stay free for jobs with tight deadlines. Explain it with the example where a job with deadline 3 takes hour 1 and blocks a job with deadline 1.
4. What is the running time? O(n log n) for the sort. The placement is fast with the parent list, and O(n * D) without it.
5. How would you return the schedule as well as the profit? Keep the hour for each job in a list, as the program prints it.

Real-world uses

The fractional knapsack is used when the items can be divided, for example when packing bulk goods such as grain or fuel into a fixed space, or when a budget can be spent in parts. Fund managers use similar thinking when they choose how much of each option to hold, though real markets have more rules.

Job sequencing with deadlines fits any system with one worker and time limits. A small repair shop that can do one visit each hour, a single machine in a factory with due dates, or a server that must finish each request before its timeout all use this kind of rule. The profit does not have to be money. It can be a score for how important each job is.

Practice

1. Fractional knapsack: values 10, 40, 30, weights 5, 10, 15, capacity 20. Find the ratios, sort, fill the bag and give the total. Hint: the ratios are 2, 4 and 2.

Show the answer

The ratios are 40 / 10 = 4, 10 / 5 = 2, and 30 / 15 = 2. Sort: the item worth 40 first, then one of the ratio-2 items. Take the 40 item (weight 10), leaving 10 units. Take the 10 item (weight 5), leaving 5 units. Take 5 of the 15 units of the 30 item, which is one third, worth 10. Total 40 + 10 + 10 = 60. Running fractional_knapsack on these items with capacity 20 returns 60.0.

2. Explain in your own words why the job placement uses the latest free hour, not the earliest. Use an example with two jobs.

Show the answer

Suppose two jobs both have deadline 2, and a third job has deadline 1. If the first job takes hour 1, the deadline-1 job has no hour. If the first job takes hour 2 instead, hour 1 stays free for the deadline-1 job. The latest free hour keeps the early hours for the tight jobs.

3. Which sort key does job sequencing use, deadline or profit? Explain why the other choice gives a wrong answer on the five-job example.

Show the answer

Profit is the right key. Sorted by deadline, the order is B (19), D (25), A (100), C (27), E (15). B takes hour 1, D is skipped, A takes hour 2, and C finds hours 1 and 2 taken, so it is skipped. The total is 19 + 100 + 15 = 134, which is less than 142. Changing the key in the job program to the deadline gives 134 on this input.

4. Jobs (deadline, profit): (1, 50), (1, 60), (2, 10). Find the maximum profit by hand, then check it with the program.

Show the answer

Sorted by profit: 60 (deadline 1), 50 (deadline 1), 10 (deadline 2). The 60 job takes hour 1. The 50 job needs hour 1, which is taken, and there is no earlier hour, so it is skipped. The 10 job takes hour 2. Total 70.

5. Write an expression that gives 3.5, not 3, for 7 divided by 2.

Show the answer

7 / 2 gives 3.5 in Python, because / always gives a float. 7 // 2 gives 3, which is the trap from this lesson.

6. A knapsack has capacity 0. What total does the program print? Explain why the loop does not add anything.

Show the answer

The program prints 0.00. The loop starts with capacity <= 0, so it breaks at once and adds nothing.

7. Change the knapsack program so it prints the fraction of each item it takes. Hint: print take / weight inside the loop.

Show the answer

Add print(take / weight) inside the loop, before capacity -= take. That line shows the fraction of each item. Keep the print before the subtraction so that take still holds the weight loaded from this item.

8. Jobs (deadline, profit): (3, 5), (3, 6), (3, 7). Find the profit by hand. Then say which hours are used.

Show the answer

All three jobs have deadline 3, so they can use hours 1, 2 and 3. Sorted by profit: 7 takes hour 3, 6 takes hour 2, 5 takes hour 1. The total is 18.

9. Jobs (1, 8), (1, 4), (2, 2), (3, 1). Find the profit. Show which hour each job uses, or say it is skipped.

Show the answer

Sorted by profit: 8 (deadline 1), 4 (deadline 1), 2 (deadline 2), 1 (deadline 3). The 8 job takes hour 1. The 4 job is skipped because hour 1 is taken. The 2 job takes hour 2. The 1 job takes hour 3. The total is 11.

10. Explain why the program caps the deadline at n for the parent list. Give the list length with and without the cap when there are three jobs and one deadline is one billion.

Show the answer

The list needs D + 1 entries, where D is the largest deadline. With a deadline of one billion, that is about a billion entries, which needs far more memory than most computers have. With the cap at n, which is 3, the list has 4 entries. The cap is valid because at most n jobs can be placed, so no job can use an hour after hour n.

What you now know

• The fractional knapsack is solved by sorting on value per unit of weight, then filling the bag from the top.
• Parts of items keep the greedy rule exact. Whole items break it, as lesson 4 shows.
• Job sequencing is solved by sorting on profit and placing each job in the latest free hour on or before its deadline.
• Use / for ratios and fractions, watch for //, and cap any deadline at the job count before you build a list.
• Both problems take O(n log n) time, dominated by the sort.

Next lesson: the Huffman coding idea, where a heap picks the two smallest weights again and again.