When fractional knapsack gives a plan you cannot pack

A box with capacity 5 can hold items I-1 and I-3 for a total value of 8. A fractional knapsack calculation returns 26/3, about 8.67, by taking all of I-2 and one third of I-1.

The arithmetic is consistent. The second plan is impossible if each item must stay whole.

This tutorial makes that assumption explicit, then checks a small 0–1 solver against every possible subset. All items, weights and values are invented teaching data. Weight and value use arbitrary demo units, with no measured business outcome implied.

AI disclosure — Fully Autonomous: This article and its standalone code were generated and prepared for publication by an AI agent for Nickwang Studio. The code and reported output were executed as recorded below.

The input contract changes the answer

There is one copy of each item:

Item	Weight	Value	Value / weight
I-1	3	5	5/3
I-2	4	7	7/4
I-3	2	3	3/2

The capacity limit is 5. Weights and values add; items have no dependencies. A feasible packing either takes an item once or leaves it behind.

A fractional solver ranks by value per unit of weight. It first takes I-2, leaving one unit of capacity. It then takes one third of I-1:

weight = 4 + (1/3 × 3) = 5

value = 7 + (1/3 × 5) = 26/3

That calculation allows a decision variable such as x[I-1] = 1/3. Our contract requires each x to be either 0 or 1. Both calculations use the same capacity constraint; the allowed item fractions differ.

You can see the whole-item optimum without a solver:

Selected items	Weight	Value	Fits?
None	0	0	Yes
I-1	3	5	Yes
I-2	4	7	Yes
I-3	2	3	Yes
I-1, I-2	7	12	No
I-1, I-3	5	8	Yes
I-2, I-3	6	10	No
All three	9	15	No

The best feasible row is I-1 plus I-3, with value 8. Rounding down the fractional plan would leave only I-2, worth 7; it would miss that better whole-item combination. Rounding up would exceed capacity.

Run both models in Python

Save this as whole_items.py and run python whole_items.py. It uses only the Python standard library. The exact code and output in this article were checked with Python 3.12.7.

Fraction preserves the one-third quantity exactly. The fractional function is included to reproduce the modelling mismatch. The whole-item function records the best value and selected IDs for each integer capacity.

"""A fictional example: each item is available once and must stay whole."""
from dataclasses import dataclass
from fractions import Fraction


@dataclass(frozen=True)
class Item:
    id: str
    weight: int
    value: int


def validate(items, capacity):
    if type(capacity) is not int or capacity < 0:
        raise ValueError("capacity must be a nonnegative integer")
    ids = set()
    for item in items:
        if not isinstance(item.id, str) or not item.id or item.id in ids:
            raise ValueError("item IDs must be nonempty and unique")
        ids.add(item.id)
        if type(item.weight) is not int or item.weight <= 0:
            raise ValueError("weights must be positive integers")
        if type(item.value) is not int or item.value < 0:
            raise ValueError("values must be nonnegative integers")


def fractional_plan(items, capacity):
    """Solve the relaxed problem, where taking a fraction is allowed."""
    validate(items, capacity)
    remaining = Fraction(capacity)
    value = Fraction(0)
    selected = []
    ordered = sorted(items, key=lambda item: Fraction(item.value, item.weight),
                     reverse=True)
    for item in ordered:
        fraction = min(Fraction(1), remaining / item.weight)
        if fraction == 0:
            break
        selected.append((item.id, fraction))
        value += fraction * item.value
        remaining -= fraction * item.weight
    return value, tuple(selected)


def whole_item_plan(items, capacity):
    """At most one copy of each item; only complete items are feasible."""
    validate(items, capacity)
    best = [(0, ()) for _ in range(capacity + 1)]
    for item in items:
        # Descend so this item cannot become its own predecessor.
        for room in range(capacity, item.weight - 1, -1):
            old_value, old_ids = best[room - item.weight]
            candidate = old_value + item.value
            if candidate > best[room][0]:
                best[room] = (candidate, old_ids + (item.id,))
    return best[capacity]


ITEMS = (Item("I-1", 3, 5), Item("I-2", 4, 7), Item("I-3", 2, 3))

if __name__ == "__main__":
    capacity = 5
    relaxed_value, relaxed_items = fractional_plan(ITEMS, capacity)
    value, ids = whole_item_plan(ITEMS, capacity)
    weight = sum(item.weight for item in ITEMS if item.id in ids)
    feasible = all(amount in (0, 1) for _, amount in relaxed_items)
    print("Fractional plan: " + ", ".join(
        f"{item_id} x {amount}" for item_id, amount in relaxed_items))
    print(f"Fractional value: {relaxed_value} ({float(relaxed_value):.2f})")
    print(f"Whole-item feasible: {feasible}")
    print("0-1 plan: " + ", ".join(ids))
    print(f"0-1 weight: {weight} / {capacity}")
    print(f"0-1 value: {value}")

Output:

Fractional plan: I-2 x 1, I-1 x 1/3
Fractional value: 26/3 (8.67)
Whole-item feasible: False
0-1 plan: I-1, I-3
0-1 weight: 5 / 5
0-1 value: 8

The Whole-item feasible line checks the fractions in this generated plan. The fractional function already limits each fraction to 1 and subtracts its weight from the remaining capacity; the missing condition is indivisibility.

Why the capacity loop runs backwards

When considering one item, each entry should choose between two possibilities: keep the previous best plan, or add this item to a plan made from earlier items.

The loop visits capacities from largest to smallest. Its predecessor at room - item.weight has therefore not been updated for the current item. This keeps an item from being reused during the same iteration.

For a quick check, call:

assert whole_item_plan((Item("only", 2, 3),), 4) == (3, ("only",))

There is only one copy. A value of 6 would indicate that the same item had been counted twice. The functions require nonnegative integer capacity, positive integer weights, nonnegative integer values and unique item IDs. The table contains capacity + 1 entries, so this implementation is intended for small integer capacities.

Check the selected plan as well as its value

For this three-item fixture, all eight subsets are small enough to inspect. Before using a larger input, check the selected IDs, their total weight, and the assumption about how many copies exist. A plausible objective value alone does not establish that the plan is feasible.

The accompanying execution checks compared the whole-item solver with exhaustive subset enumeration for capacities 0 through 10 and all six orders of these three items. They also checked an empty set, zero capacity, the single-copy case above, invalid inputs, and additional small generated fixtures. These are code checks on teaching inputs.

If your material can actually be split, the fractional model may describe the task. If items are indivisible, preserve the 0–1 decision rule. If multiple copies, dependencies, several capacity limits or non-additive values are involved, write down those rules before treating either function as the model for your task.

Exercise context

The three invented items come from Nickwang Studio's Independent Modeling Practice Kit. Its supplied capacity-7 example selects I-1 and I-2 for value 12. This article changes capacity to 5 to expose the divisibility assumption, and provides newly written Python code that runs independently of the kit.

The public product and preview page includes the optional exercise pack. Everything needed to reproduce this article is included above.