Fractional Knapsack

Q: What is the time complexity of the fractional knapsack problem?

Sorting the items by value per weight costs O(n log n) and the fill is one pass, so the total is O(n log n) with O(n) space for the order. Scanning for the densest item every round costs O(n²) .

Q: How do you solve fractional knapsack without floating point numbers?

With positive weights, a / b > c / d is the same test as a × d > c × b , so compare densities by cross-multiplying. The best value is a whole number plus one fraction, values[i] × room / weights[i] for the cut item, so one integer division gives the rounded-down answer exactly.

MediumGreedy Sorting

+10

You have n items. Item i is worth values[i] and weighs weights[i]. Your bag holds a total weight of at most capacity, and you may take any part of an item: a piece of item i that weighs w is worth values[i] × w / weights[i].

Write a function named fractionalKnapsack that returns the largest total value the bag can carry, rounded down to a whole number.

Function

fractionalKnapsack(values: integer-array, weights: integer-array, capacity: integer) → integer

valuesinteger-array: the value of each item
weightsinteger-array: the weight of each item
capacityinteger: the most weight the bag can hold
Returnsinteger: the largest total value that fits in the bag, rounded down

Constraints

1 ≤ n ≤ 5000, where n = values.length = weights.length
1 ≤ values[i], weights[i] ≤ 10⁴
1 ≤ capacity ≤ 10⁸

Examples

Input: values = [40, 90, 30, 50]weights = [8, 30, 5, 20]capacity = 40
Output: 151
Explanation: Per unit of weight the items are worth 5, 3, 6 and 2.5. Items 2 and 0 go in whole for 70 with room for 27 left, and 27 of item 1's 30 units add 81, for 151.

Input: values = [10, 7]weights = [4, 3]capacity = 5
Output: 12
Explanation: Item 0 is worth 2.5 per unit and item 1 about 2.33, so item 0 goes in whole for 10. One of item 1's 3 units adds 7 / 3, and 12 and one third rounds down to 12.

Follow-up

Can you find the answer in O(n) time, without sorting all the items?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Because you may cut items, the problem is greedy, unlike the 0/1 knapsack: every unit of weight should come from the item with the most value per unit left. Sort by that density and fill the bag in order. Compare densities by cross-multiplying and round down only the item you cut, so no fraction is ever stored.

Pick the densest item each round

Correct, but does not finish on the largest tests

Intuition

Fill the bag from the densest item down: take it whole if it fits, otherwise take the piece that fills the bag and stop. Find the densest unused item by scanning all of them, comparing values[i] × weights[j] with values[j] × weights[i] instead of dividing. With positive weights it is the same test, and both products stay at or below 10^8.

Densest first is best: if a load holds some weight of a less dense item while a denser item is not fully in, swapping that weight for the denser item cannot lower the value. Keep swapping and you reach the densest-first load.

Up to n rounds each scan the unused items, about n²/2 = 12.5 million comparisons for n = 5000.

Algorithm

Mark every item as unused and set room = capacity and total = 0.
While there is room, scan the unused items for the densest one, comparing densities by cross-multiplying.
If no item is left, stop. Otherwise mark that item as used.
If it fits, add its value to total and its weight comes off room. If it does not, add values[i] × room / weights[i] with integer division and stop.
Return total.

def fractionalKnapsack(values, weights, capacity):
    n = len(values)
    used = [False] * n
    total = 0
    room = capacity
    while room > 0:
        best = -1
        for i in range(n):
            # i is denser than best: values[i] / weights[i] > values[best] / weights[best], cross-multiplied
            if not used[i] and (best == -1 or values[i] * weights[best] > values[best] * weights[i]):
                best = i
        if best == -1:
            break  # every item is already in the bag
        used[best] = True
        if weights[best] <= room:
            total += values[best]
            room -= weights[best]
        else:
            total += values[best] * room // weights[best]  # the part that fits, rounded down
            room = 0
    return total

Sort by value per weight

Intuition

The scan finds the densest item again and again, but the order never changes between rounds. Sort the items once, densest first, with the same cross-multiplied comparison. Items of equal density can go in either order, since they are worth the same per unit.

Take items whole while they fit. The first one that does not fit is the only one you cut: it adds values[i] × room / weights[i], and integer division rounds that down. Everything before it is a whole number, so rounding this one term gives the exact answer. The sort costs O(n log n) and the walk O(n).

Algorithm

Make a list of the item indices and sort it densest first with the cross-multiplied comparison.
Set room = capacity and total = 0.
For each item in that order, if weights[i] ≤ room, add its value and take its weight off room.
Otherwise add values[i] × room / weights[i] with integer division and stop.
Return total.

from functools import cmp_to_key


def fractionalKnapsack(values, weights, capacity):
    # a goes before b when values[a] / weights[a] > values[b] / weights[b],
    # tested as values[a] * weights[b] > values[b] * weights[a] to stay in whole numbers.
    def denser_first(a, b):
        return values[b] * weights[a] - values[a] * weights[b]

    order = sorted(range(len(values)), key=cmp_to_key(denser_first))
    total = 0
    room = capacity
    for i in order:
        if weights[i] <= room:
            total += values[i]  # the whole item fits
            room -= weights[i]
        else:
            total += values[i] * room // weights[i]  # the part that fits, rounded down
            break
    return total

Pitfalls and edge cases

Sorting by value or by weight alone. In the first example the item worth 90 is only third by density; taking it first leaves room for half of the item worth 50, for 115 instead of 151.
Dividing before multiplying. With value 13, weight 7 and room 3, 13 / 7 * 3 in integer arithmetic gives 3, while 13 * 3 / 7 gives the right 5.
Expecting an item to be cut every time. In the third example every item fits, and the answer is the sum of all values, 13.

Frequently asked questions3

What is the time complexity of the fractional knapsack problem?

Sorting the items by value per weight costs O(n log n) and the fill is one pass, so the total is O(n log n) with O(n) space for the order. Scanning for the densest item every round costs O(n²).

Why does greedy work for fractional knapsack but not for 0/1 knapsack?

Cutting lets you swap weight from a less dense item for a denser one. Without cutting, a dense item can leave room nothing else fills. With values 8, 11, 15, weights 2, 3, 4 and capacity 7, densest first takes weights 2 and 4 for 23, while weights 3 and 4 give 26. The 0/1 version needs dynamic programming.

How do you solve fractional knapsack without floating point numbers?

With positive weights, a / b > c / d is the same test as a × d > c × b, so compare densities by cross-multiplying. The best value is a whole number plus one fraction, values[i] × room / weights[i] for the cut item, so one integer division gives the rounded-down answer exactly.

def fractionalKnapsack(values, weights, capacity):
    # Write code here

Test #1

Test #2

Test #3

Arguments

values = [40, 90, 30, 50]
weights = [8, 30, 5, 20]
capacity = 40

Expected Output