Java DP exercises: exhaustive small inputs as a reference

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

Make the oracle use another approach

The knapsack oracle enumerates subsets instead of repeating the one-row capacity recurrence. Each bit means an item is selected once. This gives a separate route to the expected result and exposes accidental repeated use of one item.

The completed exercise includes an exact-fit pair, an item that is too heavy, and a single item that cannot be selected twice. The third case is especially useful because an ascending one-row update can mistakenly produce a value of sixteen instead of eight.

A reference still needs an input budget. Subset count doubles for every added item, so this program rejects more than twenty candidates. Checked weight and value addition also prevent overflow from silently turning an infeasible subset into a winning one.

Expand tests by contract

Include duplicate weights, equal values, zero capacity and items with zero value. Reject unsupported negative values or nonpositive weights before enumeration. For a property suite, generate bounded random inputs and compare the oracle with the production recurrence rather than testing only one hand-picked result.

Working program

public class BagSubsetOracle {
    static long maximum(int capacity,int[] weights,long[] values){
        if(capacity<0||weights.length!=values.length||weights.length>20)throw new IllegalArgumentException("Oracle budget");
        for(int i=0;i<weights.length;i++)if(weights[i]<=0||values[i]<0)throw new IllegalArgumentException("Item contract");
        long best=0;
        for(int mask=0;mask<(1<<weights.length);mask++){
            long weight=0,value=0;for(int i=0;i<weights.length;i++)if((mask&(1<<i))!=0){weight=Math.addExact(weight,weights[i]);value=Math.addExact(value,values[i]);}
            if(weight<=capacity)best=Math.max(best,value);
        }return best;
    }
    public static void main(String[] args){
        if(maximum(7,new int[]{3,4},new long[]{8,10})!=18)throw new AssertionError("Exact pair");
        if(maximum(2,new int[]{3},new long[]{8})!=0)throw new AssertionError("Heavy item");
        if(maximum(6,new int[]{3},new long[]{8})!=8)throw new AssertionError("Repeated item");System.out.println("checks=3");
    }
}

Output

checks=3

Costs and boundaries

Enumeration takes O(n 2^n) time and constant scalar storage beyond the input. This is a small-input test oracle, not an optimization for large candidate sets. A correct oracle can still fail to exercise a missing boundary if the generated test inputs never contain it.

Common Mistakes

• Do not reuse the same recurrence as both implementation and oracle.
• An exponential test helper needs a strict candidate limit.
• An item bit is a single-use choice.

Read next

Capacity recurrence, State order.