Introduction

If item type now affects feasibility or scoring, the original knapsack state is no longer rich enough. You cannot solve the old knapsack problem first and then patch the answer afterward, because once type matters, it has to be part of the optimization state itself.

Why Type Changes the Model

A classic 0/1 knapsack dynamic program often uses a state like dp[i][w], meaning the best value achievable using the first i items within capacity w.

That works only when items differ by weight and value. Once type matters, the problem may include rules such as:

• at most one item from each type
• at most k items from one type
• bonuses or penalties for type diversity
• quotas per category

Those rules affect which transitions are legal, so the old state is no longer enough.

Do Not Solve First and Filter Later

A common but wrong idea is:

1. run the original knapsack solver
2. inspect the chosen items
3. remove or replace items that violate the type rule

That usually destroys optimality and can even make the final solution infeasible. If type changes what choices are allowed, type must be represented while the solution is being built.

Group Items by Type First

A practical first step is to group the items by type. That makes the transition logic much easier to write.

1from collections import defaultdict
2
3items = [
4    # (weight, value, type)
5    (2, 3, "A"),
6    (3, 5, "A"),
7    (1, 2, "B"),
8    (4, 7, "C"),
9]
10
11by_type = defaultdict(list)
12for weight, value, item_type in items:
13    by_type[item_type].append((weight, value))
14
15print(by_type)

Once the data is grouped, you can process one type block at a time.

Example: At Most One Item Per Type

This is a grouped or multiple-choice knapsack style problem. For each type, you may choose zero or one item from that group.

1from collections import defaultdict
2
3items = [
4    (2, 3, "A"),
5    (3, 5, "A"),
6    (1, 2, "B"),
7    (4, 7, "C"),
8]
9capacity = 7
10
11by_type = defaultdict(list)
12for weight, value, item_type in items:
13    by_type[item_type].append((weight, value))
14
15dp = [0] + [-10**9] * capacity
16
17for group in by_type.values():
18    new_dp = dp[:]
19    for used_weight in range(capacity + 1):
20        if dp[used_weight] < 0:
21            continue
22        for item_weight, item_value in group:
23            if used_weight + item_weight <= capacity:
24                new_dp[used_weight + item_weight] = max(
25                    new_dp[used_weight + item_weight],
26                    dp[used_weight] + item_value,
27                )
28    dp = new_dp
29
30print(max(dp))

The important detail is that the transition for one type is isolated before moving on to the next type, which prevents the DP from choosing two items from the same group.

Example: Limit the Count per Type

If the rule is "up to k items per type," the DP needs more local state. One common pattern is to compute the best achievable values for each type separately and then merge them into the global capacity DP.

The exact implementation depends on the type rule, but the general principle is always the same: once type changes legality, the state or transition logic must explicitly encode that fact.

When Dynamic Programming Gets Too Complicated

If type rules become much richer, such as cross-type dependencies, minimum counts, or multiple resource budgets, the state can grow quickly. At that point, an integer-programming formulation may be easier to reason about than stretching a hand-written DP too far.

The correct question is not "how do I force this into my old solver." The better question is "what optimization model now matches the real constraints."

Common Pitfalls

• Solving the original knapsack problem first and trying to repair the answer afterward usually breaks optimality.
• Adding type as a vague concept without defining the exact rule makes the DP impossible to design cleanly.
• Forgetting that new state dimensions increase memory and runtime can make the solution impractical.
• Testing only large random inputs hides transition bugs that small hand-checkable examples would reveal.
• Assuming all type constraints are the same leads to the wrong recurrence; "one per group" and "up to k per group" are different problems.

Summary

• If item type affects feasibility, it must be modeled during optimization.
• Post-filtering a classic knapsack answer is usually wrong.
• Grouping items by type is a useful first step.
• Different type rules require different DP transitions.
• If the DP state becomes too large, consider a different optimization formulation instead of forcing the original model.