Java 0/1 knapsack: reverse capacity iteration prevents reuse

Java 8+. The program uses JDK classes and requires no preview flags.

Use the previous item state

A dispatch bag has a weight budget and a fixed collection of candidate items. The recurrence can skip an item or include it using capacity that existed before that item’s pass. Iterating capacities downward preserves that previous-item state in one array.

Ascending capacity iteration would let an item’s updated value feed another position during the same pass, allowing repeated use. That is a different, unbounded problem. The loop direction is therefore part of the correctness argument rather than a micro-optimization.

This fixture requires positive weights and non-negative values. Zero-weight items need a separate rule; the program rejects them instead of leaving their behavior accidental. Checked addition rejects a value total outside long range.

Budget the state space

The program limits capacity to 100,000 and the item-capacity product to five million updates. Those bounds are for the tutorial model. Very large weights with small item counts can call for another formulation rather than allocating a row with one slot per possible capacity.

Working program

public class DispatchBagValue {
    static long maximum(int capacity,int[] weights,long[] values){
        if(capacity<0||capacity>100_000||weights.length!=values.length||(long)capacity*weights.length>5_000_000)throw new IllegalArgumentException("Knapsack budget");
        for(int i=0;i<weights.length;i++)if(weights[i]<=0||values[i]<0)throw new IllegalArgumentException("Item contract");
        long[] best=new long[capacity+1];
        for(int i=0;i<weights.length;i++)for(int available=capacity;available>=weights[i];available--)
            best[available]=Math.max(best[available],Math.addExact(best[available-weights[i]],values[i]));
        return best[capacity];
    }
    public static void main(String[] args){System.out.println(maximum(7,new int[]{3,4,5},new long[]{8,10,12}));System.out.println(maximum(6,new int[]{3},new long[]{8}));System.out.println(maximum(0,new int[]{3},new long[]{8}));}
}

Output

18
8
0

Costs and boundaries

Time is O(nC), storage is O(C), where C is the numeric capacity. This is pseudo-polynomial because capacity size is not the number of bits needed to encode it. The result is a value only; selected items require reconstruction state.

Common Mistakes

• Ascending capacity order changes the problem to allow reuse.
• Reject unsupported zero-weight input explicitly.
• A value total can overflow even when individual item values fit.

Read next

Dependency order, Objective-specific greedy choices.