0/1 Knapsack

0/1 knapsack chooses each item at most once to maximize value under a weight capacity. Unlike fractional knapsack, an item cannot be split, so a value/weight greedy order is unsafe. An item-layer state preserves the remaining decision boundary. We give a full table with item reconstruction and a separate compressed program to make the critical backward loop visible.

Prerequisites: Reconstruction; Two-Dimensional DP; item/capacity modeling. Related existing lessons: Fractional Knapsack.

Build the idea

1. Recognize the repeated subproblems

   Enumerating take/skip choices creates 2^n subsets, but many prefixes leave the same capacity. Constraints with moderate integer capacity W suggest a pseudo-polynomial nW table. This depends on the numeric capacity, not merely its bit length; a capacity near 10^12 would make the same design impractical even for relatively few items.

2. Define the state

   dp[i][c] is maximum value using the first i items with total weight at most c. Items have positive weight and nonnegative value; leaving capacity unused is allowed. The processed-item count prevents reuse, while c retains everything needed about the resource. “At most” capacity permits zero initialization for every base capacity; exact-fill variants need unreachable states.

3. Derive the transition

   For item i, either skip it and keep dp[i−1][c], or take it if wi≤c and add vi to dp[i−1][c−wi]. Both alternatives use the previous item layer. Taking the maximum covers every subset according to membership of item i. This is why reading the current row in the wrong place can accidentally turn the problem into unlimited reuse.

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

4. Base cases and computation order

   Initialize row zero to value zero at all capacities. Fill i outward and c across the row, then reconstruct from (n, W): if the value differs from the row above, item i was taken; subtract its weight. Otherwise skip it, including equal-value ties. The compressed version removes i but iterates c backward, so the predecessor capacity still belongs to the previous item layer.

5. Correctness and invariant

   Induct on processed items. Every feasible subset either excludes i or removes i to a feasible previous-layer subset, giving an upper bound by the recurrence. Each candidate can be constructed legally, so the upper bound is attained. Backward compression preserves this exact dependency invariant; forward compression would allow the current item in its own predecessor and invalidate the 0/1 proof.

6. Work the example

   With W=5 and items (2,3),(3,4),(4,5), row one reaches value 3 at capacity≥2. Row two reaches 7 at capacity 5 by taking both first items. The third does not improve it. Reconstruction prints IDs 1,2. The compressed program prints only 7 because it deliberately does not retain the item-layer witness table.

   items / capacity	0	1	2	3	4	5
   0	0	0	0	0	0	0
   1	0	0	3	3	3	3
   2	0	0	3	4	4	7
   3	0	0	3	4	5	7

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<int>weight(n+1);
    std::vector<long long>value(n+1);
    for(int i=1;i<=n;++i){
        std::cin>>weight[i]>>value[i];
    }
    std::vector<std::vector<long long>>dp(n+1,std::vector<long long>(W+1));
    for(int i=1;i<=n;++i){
        for(int c=0;c<=W;++c){
            dp[i][c]=dp[i-1][c];
            if(weight[i]<=c){
                dp[i][c]=std::max(dp[i][c],dp[i-1][c-weight[i]]+value[i]);
            }
        } // Both choices use the previous item row.
    }
    std::vector<int>chosen;
    int c=W;
    for(int i=n;i>=1;--i){
        if(dp[i][c]!=dp[i-1][c]){
            chosen.push_back(i);
            c-=weight[i];
        }
    }
    std::reverse(chosen.begin(),chosen.end());
    std::cout<<dp[n][W]<<'\n'<<chosen.size();
    for(int id:chosen){
        std::cout<<' '<<id;
    }
    std::cout<<'\n';
}

Complexity analysis

(n+1)(W+1) states, two transitions each: O(nW) time and space for the full table, plus O(n) reconstruction. The supplementary backward-capacity program uses O(W) DP space and the same time, without direct item reconstruction. Value≤10^11 fits long long.

Example input and output

Read n W (0≤n≤100,0≤W≤10000), then positive weight≤10^6 and value in 0..10^9 for each item. Print maximum value, then count and selected 1-based IDs.

Input

3 5
2 3
3 4
4 5

Output

7
2 1 2

With W=5 and items (2,3),(3,4),(4,5), row one reaches value 3 at capacity≥2. Row two reaches 7 at capacity 5 by taking both first items. The third does not improve it. Reconstruction prints IDs 1,2. The compressed program prints only 7 because it deliberately does not retain the item-layer witness table.

Same input and bounds as the full knapsack program. Print maximum value only.

#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);
        }
    } // Backward: dp[c-w] has not used this item yet.
    std::cout<<dp[W]<<'\n';
}

Input

3 5
2 3
3 4
4 5

Output

7

Backward capacities preserve the previous item layer. This version does not retain the full table needed for the primary witness backtrack.

Complexity: O(nW) time,O(W) DP memory;input is streamed.

Practical applications

Use for bounded-capacity indivisible selection. If values are small but weights huge, consider value-indexed DP; if n is tiny, meet-in-the-middle may be better. Unbounded knapsack deliberately changes the iteration invariant.

Check your understanding

Why does the compressed 0/1 loop run backward?

Put it into practice

Test one item of weight 2,value 3 with capacity 4.