Group Knapsack, in Depth

The problem and its relatives

Formally there are G groups. Group g contains items (w, v) with integer weight w and value v. A selection picks at most one item from each group, and is feasible if the sum of chosen weights is at most the capacity W. Maximise the sum of chosen values.

It helps to see how this sits among the relatives. Ordinary 0/1 knapsack is the special case where every group holds one item. Bounded knapsack, where an item may be taken up to k times, reduces to group knapsack: make a group per item whose alternatives are "take 1", "take 2" up to "take k". Multidimensional knapsack adds more capacity constraints, which is a different axis. Like 0/1 knapsack, group knapsack is NP-hard, but with integer weights it has a pseudo-polynomial DP that runs in time proportional to the number of items times W.

The problem and its relatives

Formally there are G groups. Group g contains items (w, v) with integer weight w and value v. A selection picks at most one item from each group, and is feasible if the sum of chosen weights is at most the capacity W. Maximise the sum of chosen values.

It helps to see how this sits among the relatives. Ordinary 0/1 knapsack is the special case where every group holds one item. Bounded knapsack, where an item may be taken up to k times, reduces to group knapsack: make a group per item whose alternatives are "take 1", "take 2" up to "take k". Multidimensional knapsack adds more capacity constraints, which is a different axis. Like 0/1 knapsack, group knapsack is NP-hard, but with integer weights it has a pseudo-polynomial DP that runs in time proportional to the number of items times W.

The recurrence

Let dp[g][w] be the best value achievable using only the first g groups with total weight at most w. For group g there are two kinds of choice: take nothing from it, or take exactly one of its items. That gives the recurrence:

dp[0][w] = 0                                   for all w in 0..W
dp[g][w] = max( dp[g-1][w],                    # skip group g
                max over items (wi, vi) in group g with wi <= w of
                    dp[g-1][w - wi] + vi )     # take one item from group g
answer   = dp[G][W]

The key detail is that every option for group g reads from row g-1, never from row g. Reading from the previous row is what enforces "one item from this group": once you have taken an item, the remaining capacity can only be filled from earlier groups. Compare this with 0/1 knapsack, where each item is a separate layer, and unbounded knapsack, where an item may read from its own row and so be reused. Group knapsack collapses a whole group into one layer.

Correctness follows by the usual exchange argument. An optimal selection over the first g groups either uses no item of group g, in which case it is an optimal selection over g-1 groups, or uses exactly one item (wi, vi), in which case the rest must be optimal over g-1 groups with capacity w - wi. The recurrence tries both cases and every item.

Implementation with reconstruction

The two-dimensional table is easy to reason about and also gives you the reconstruction, which is what real applications need: knowing which item each group chose matters more than the total.

def group_knapsack(groups, W):
    """groups: list of lists of (weight, value). Returns (best_value, choice per group or None)."""
    G = len(groups)
    dp = [[0] * (W + 1) for _ in range(G + 1)]
    pick = [[-1] * (W + 1) for _ in range(G + 1)]   # item index chosen in group g at capacity w
    for g in range(1, G + 1):
        prev, cur = dp[g - 1], dp[g]
        for w in range(W + 1):
            cur[w] = prev[w]                         # skip the group
            for i, (wi, vi) in enumerate(groups[g - 1]):
                if wi <= w and prev[w - wi] + vi > cur[w]:
                    cur[w] = prev[w - wi] + vi
                    pick[g][w] = i
    choice, w = [None] * G, W
    for g in range(G, 0, -1):                        # walk back through the layers
        i = pick[g][w]
        if i >= 0:
            choice[g - 1] = i
            w -= groups[g - 1][i][0]
    return dp[G][W], choice

groups = [[(1, 3), (3, 8)], [(2, 4), (3, 6)], [(1, 3), (2, 5)]]
print(group_knapsack(groups, 5))   # (13, [1, None, 1])

Time is O(W times the total number of items), because each item is examined once per capacity value. Space is O(G times W) for the two tables.

One array and the loop-order trap

If you only need the value, one array of size W + 1 is enough, as long as the loops run in the right order: group outermost, capacity descending in the middle, items of the group innermost. Descending capacity means that when dp[w] is updated, dp[w - wi] still holds the value from before this group, which is exactly the previous row.

def group_knapsack_1d(groups, W):
    dp = [0] * (W + 1)
    for group in groups:                 # 1. one layer per group
        for w in range(W, -1, -1):       # 2. capacity descending
            best = dp[w]                 # skip the group
            for wi, vi in group:         # 3. every alternative in the group
                if wi <= w:
                    best = max(best, dp[w - wi] + vi)
            dp[w] = best                 # write once, after all alternatives
    return dp[W]

def broken_1d(groups, W):
    dp = [0] * (W + 1)
    for group in groups:
        for wi, vi in group:             # items outside capacity: this is plain 0/1 knapsack
            for w in range(W, wi - 1, -1):
                dp[w] = max(dp[w], dp[w - wi] + vi)
    return dp[W]

print(group_knapsack_1d(groups, 5), broken_1d(groups, 5))   # 13 14

The broken version swaps loops 2 and 3. Each item then runs its own descending pass, which is precisely 0/1 knapsack over all items with the groups ignored. On the example it returns 14 by taking a1 and a2 from the same group plus c1. The bug is dangerous because it passes any test where groups have one item, or where the best answer happens to respect the groups, and it only overestimates, so it never looks obviously wrong. Always include a test where two items of one group together beat every legal selection.

Exactly one item per group

Sometimes every group must contribute: every layer of a network needs some precision, every service needs some instance size. Two changes turn at-most-one into exactly-one. Initialise the states for "zero groups processed" so that only weight 0 is reachable, and remove the skip option.

NEG = float("-inf")

def group_knapsack_exact(groups, W):
    dp = [0] + [NEG] * W                 # dp[w]: best value with total weight exactly w
    for group in groups:
        nxt = [NEG] * (W + 1)            # fresh row: no skipping allowed
        for w in range(W + 1):
            for wi, vi in group:
                if wi <= w and dp[w - wi] != NEG:
                    nxt[w] = max(nxt[w], dp[w - wi] + vi)
        dp = nxt
    best = max(dp)
    return None if best == NEG else best     # None: no feasible selection

print(group_knapsack_exact(groups, 5))       # 12

Here dp[w] means weight exactly w, so the answer is the maximum over the whole final row. A fresh row per group replaces the descending-loop trick because without the skip option the old values must not survive into the new row. Two traps: an empty group makes the problem infeasible, so check for it up front; and in languages with fixed-width integers, use a large negative sentinel and test for it rather than adding to it, or the sentinel overflows.

Worked example

Take the three groups from the code with W = 5, the same data as the diagram. Start with a row of zeros.

Group 1 offers a1 (weight 1, value 3) and a2 (weight 3, value 8). For each w take the best of skipping, a1 on top of the start row, or a2 on top of it. The row becomes 0, 3, 3, 8, 8, 8.

Group 2 offers b1 (2, 4) and b2 (3, 6). At w = 4, skipping gives 8, b1 gives 3 + 4 = 7 and b2 gives 3 + 6 = 9, so 9. At w = 5, b1 gives 8 + 4 = 12, which beats skipping (8) and b2 (3 + 6 = 9). The row becomes 0, 3, 4, 8, 9, 12.

Group 3 offers c1 (1, 3) and c2 (2, 5). At w = 5, skipping gives 12, c1 gives 9 + 3 = 12, and c2 gives 8 + 5 = 13. The answer is 13. Walking back: c2 was chosen at w = 5, leaving w = 3; group 2's value at w = 3 was inherited by skipping; group 1 chose a2 at w = 3. Selection: a2 and c2, weight 5, value 13.

Under exactly-one, group 2 cannot be skipped. The lightest legal selection weighs 1 + 2 + 1 = 4, and the best options within 5 are a1, b1, c2 or a1, b2, c1, both worth 12. Requiring every group to contribute cost one unit of value here, and the exact variant reports that directly.

Scaling up and an application

The DP is pseudo-polynomial: its cost grows with the numeric value of W, not with the size of the input. With 200 groups of 8 items and W = 100,000 that is 160 million updates, fine in C++ or NumPy and slow in pure Python. When W is huge, three tools help.

• Dominance pruning. Within a group, drop any item that is no lighter and no more valuable than another item in the same group. For bounds, a further filter keeps only items on the upper convex hull of (weight, value) points, since an item under the hull can never be chosen by the linear relaxation.
• The LP relaxation as a bound. If you allow fractional choices, as in fractional knapsack, a classical result says the relaxation is solved greedily by moving along each group's hull in order of incremental value per unit of weight, and at most one group ends up split between two adjacent hull items. That bound drives branch and bound, and the greedy rounding is a fast heuristic.
• Swap the DP axis. If values are small integers and weights are large, index by value instead: minw[v] is the least weight that reaches value v, and the answer is the largest v with minw[v] <= W.

A practical example of the shape is mixed-precision quantization. Each layer of a model is a group, its alternatives are bit widths, weight is memory in megabytes, and value is the negative of a measured accuracy-loss proxy for quantizing that layer. Exactly-one applies because every layer needs a precision. The DP finds the per-layer assignment that loses least under the memory cap, provided the proxies add up roughly independently across layers. That additivity assumption is the real weakness of the method, so validate the chosen assignment end to end rather than trusting the summed proxy.

Failure modes

• Loop order. Items outside capacity turns the solver into 0/1 knapsack and overestimates.
• Mixing variants. Zero initialisation with no skip option, or negative infinity with a skip option, gives answers that are neither variant.
• Lost reconstruction. The 1-D form cannot recover the selection. Keep a G by W+1 choice table, or rerun the 2-D version when you need the items.
• Zero-weight items. If the 1-D loop writes dp[w] inside the item loop, a weight-0 item reads the value another item of the same group just wrote, and two items stack. Collect the best into a local and write once, as the code above does.
• Non-integer weights. Scale and round them to integers, and accept that rounding can make a borderline selection look feasible. Recheck the winner against the true weights.

What to do next

1. Implement the 2-D version with reconstruction and check it against brute force on random small inputs.
2. Write the 1-D version, then the broken loop order, and find a test case that separates them.
3. Add the exactly-one variant, including empty-group and infeasible-budget handling.
4. Reduce a bounded knapsack instance to group knapsack and compare results.
5. Add dominance pruning and measure the speed-up on groups with many alternatives.
6. Model one real decision in your work, such as per-layer precision or per-service sizing, as groups and solve it.