Unbounded Knapsack

Unbounded knapsack allows any number of copies of each positive-weight item. Its state resembles 0/1 knapsack, but the legal take transition may remain in the current item layer. This changes the compressed loop direction. Understanding the dependency, rather than memorizing “forward or backward,” prevents one of the most common DP modeling errors.

Prerequisites: 0/1 Knapsack; layered dependency invariants.

Build the idea

1. Recognize the repeated subproblems

   Brute force chooses an unbounded nonnegative count for each type, with many count vectors reaching the same used capacity. Positive integer weights and a moderate capacity W make a capacity-indexed table possible. A zero-weight positive-value item would make the optimum infinite; it is excluded instead of silently allowing a nonterminating recurrence.

2. Define the state

   After processing some item types, dp[c] is maximum value with total weight at most c using unlimited copies of those types. Zero means choosing nothing is always feasible. In an explicit layer form D[i][c], skip uses D[i−1][c], while take uses D[i][c−wi]+vi because another copy of item i remains allowed.

3. Derive the transition

   Process each item and scan capacities c=wi…W upward. At c, dp[c−wi] may already include item i, which is intentional. Taking max with the old dp[c] combines using zero copies with using at least one. Repeating the take dependency represents every nonnegative count without having to enumerate that count in a separate loop.

   $$D\left[i\right]\left[c\right]=\max \left(D\right[i-1\left]\right[c],\mathrm{vi}+D[i\left]\right[c-\mathrm{wi}\left]\right)$$

4. Base cases and computation order

   Initialize all capacities to zero under the at-most contract. Every take reduces capacity by a strictly positive weight, so forward iteration has computed its predecessor. The outer item loop limits the set of available types, not their copy counts. A descending loop would prohibit same-layer reuse and compute the 0/1 problem instead.

5. Correctness and invariant

   Induct over item types and then capacity. An optimum uses no copy of the current type, or remove one copy and obtain a smaller-capacity optimum with the same types still available. The recurrence includes both and constructs feasible solutions. Values alone do not double-count: maximization can compare multiple equivalent descriptions without affecting the optimum, unlike counting tasks where duplicate representations matter.

6. Work the example

   Capacity 7 with types (2,3),(3,4) first yields values 0,0,3,3,6,6,9,9 using weight-2 copies. After allowing weight 3, capacities 3,5,7 improve to 4,7,10. The optimum takes weights 2+2+3 for value 10, demonstrating deliberate repeated item use.

   capacity	0	1	2	3	4	5	6	7
   after (2,3)	0	0	3	3	6	6	9	9
   after (3,4)	0	0	3	4	6	7	9	10

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<algorithm>
int main(){
    int n,W;
    std::cin>>n>>W;
    std::vector<long long>dp(W+1);
    for(int i=0;i<n;++i){
        int w;
        long long v;
        std::cin>>w>>v;
        for(int c=w;c<=W;++c){
            dp[c]=std::max(dp[c],dp[c-w]+v);
        }
    } // Forward: the same item may already occur in dp[c-w].
    std::cout<<dp[W]<<'\n';
}

Complexity analysis

O(nW) time from n capacity scans and O(W) DP storage. Conceptually nW layered states have two transitions; compression retains current/previous type information through order. Value≤W·10^9≤10^13 fits long long.

Example input and output

Read n W (0≤n≤100,0≤W≤10000), then positive integer weight≤10^6 and value in 0..10^9 per type. Unlimited copies, total weight at most W. Print maximum value.

Input

2 7
2 3
3 4

Output

10

Capacity 7 with types (2,3),(3,4) first yields values 0,0,3,3,6,6,9,9 using weight-2 copies. After allowing weight 3, capacities 3,5,7 improve to 4,7,10. The optimum takes weights 2+2+3 for value 10, demonstrating deliberate repeated item use.

Practical applications

Use for repeated resource types, repeatable actions and unlimited item selection. Bounded multiplicities need binary grouping or another bounded-knapsack method. Coin change uses related capacities but optimizes counts or counts representations instead of value.

Check your understanding

Why is reading a current-layer predecessor valid here?

Put it into practice

Compare forward and backward loops on one repeatable item.