Two-bag 0-1 knapsack problem
= Two-bag 0-1 knapsack problem
Assign each item to neither bag or exactly one of two bags, respecting both capacities and maximizing total value. With nonnegative integer capacities $W_1,W_2$, a <dynamic programming state> indexed by the item prefix and both capacities gives $O(n(W_1+1)(W_2+1))$ <time complexity>. Every transition uses the preceding item layer to prevent reuse of an item.