Java bottom-up tabulation: dependency order and unreachable states

Java 8+. This is a complete program using JDK classes.

Choose the state before writing loops

A packaging calculator asks for the fewest allowed pack sizes that exactly fill an order quantity. The state is the requested quantity, and its value is the smallest pack count. State zero is reachable using zero packs; an unfilled state needs a distinct sentinel.

Positive pack sizes make every transition point to a smaller quantity. The ascending loop therefore visits dependencies first. A zero pack size would point back to the same state, while a negative size would invalidate both indexing and the dependency proof.

Greedily choosing the largest pack does not solve this general exact-fill problem. A local choice can leave a remainder that no pack can fill, or use more packs than a smaller initial choice. The recurrence compares all permitted final packs at each quantity.

Working program

import java.util.Arrays;
public class ExactPackTabulation {
    static int minimum(int quantity,int[] packs){
        if(quantity<0||quantity>1_000_000)throw new IllegalArgumentException("Quantity outside budget");
        for(int pack:packs)if(pack<=0)throw new IllegalArgumentException("Positive packs required");
        int absent=quantity+1;int[] best=new int[quantity+1];Arrays.fill(best,absent);best[0]=0;
        for(int amount=1;amount<=quantity;amount++)
            for(int pack:packs)if(pack<=amount&&best[amount-pack]!=absent)best[amount]=Math.min(best[amount],best[amount-pack]+1);
        return best[quantity]==absent?-1:best[quantity];
    }
    public static void main(String[] args){
        int[] packs={3,5};System.out.println(minimum(9,packs));
        System.out.println(minimum(7,packs));System.out.println(minimum(0,packs));
    }
}

Output

3
-1
0

Costs and boundaries

For target quantity q and k pack sizes, the method uses O(q k) work and O(q) storage. The explicit maximum quantity is an application memory budget. This is pseudo-polynomial work in the numeric target, not logarithmic work in the number of digits used to encode it.

Common Mistakes

• Zero and negative transitions invalidate the recurrence.
• Keep unreachable separate from a zero-cost solution.
• A large numeric target can exceed an acceptable allocation budget.

Read next

Top-down cached states, Enumerated choices.

Extend the tested workflow

Continue with Java matrix-chain DP: minimize multiplication work without reordering matrices.