TheAlgorithms/Java · error · IllegalArgumentException

Capacity must not be negative.

Error message

Capacity must not be negative.

What it means

KnapsackZeroOneTabulation.compute allocates dp[itemCount + 1][capacity + 1]. A negative capacity would cause a NegativeArraySizeException during table allocation, so the method rejects capacity < 0 with IllegalArgumentException upfront.

Source

Thrown at src/main/java/com/thealgorithms/dynamicprogramming/KnapsackZeroOneTabulation.java:44

    /**
     * Solves the 0-1 Knapsack problem using the bottom-up tabulation technique.
     * @param values the values of the items
     * @param weights the weights of the items
     * @param capacity the total capacity of the knapsack
     * @param itemCount the number of items
     * @return the maximum value that can be put in the knapsack
     * @throws IllegalArgumentException if input arrays are null, of different lengths,or if capacity or itemCount is invalid
     */
    public static int compute(final int[] values, final int[] weights, final int capacity, final int itemCount) {
        if (values == null || weights == null) {
            throw new IllegalArgumentException("Values and weights arrays must not be null.");
        }
        if (values.length != weights.length) {
            throw new IllegalArgumentException("Values and weights arrays must be non-null and of same length.");
        }
        if (capacity < 0) {
            throw new IllegalArgumentException("Capacity must not be negative.");
        }
        if (itemCount < 0 || itemCount > values.length) {
            throw new IllegalArgumentException("Item count must be between 0 and the length of the values array.");
        }

        final int[][] dp = new int[itemCount + 1][capacity + 1];

        for (int i = 1; i <= itemCount; i++) {
            final int currentValue = values[i - 1];
            final int currentWeight = weights[i - 1];

            for (int w = 1; w <= capacity; w++) {
                if (currentWeight <= w) {
                    final int includeItem = currentValue + dp[i - 1][w - currentWeight];
                    final int excludeItem = dp[i - 1][w];
                    dp[i][w] = Math.max(includeItem, excludeItem);
                } else {
                    dp[i][w] = dp[i - 1][w];

View on GitHub (pinned to fdfb9a395b)

Solutions

1. Clamp capacity to zero: Math.max(0, capacity).
2. Replace any -1 sentinel with the real value before the call.
3. Validate capacity >= 0 at the data source.

Example fix

// before
int r = KnapsackZeroOneTabulation.compute(values, weights, budget - cost, count); // throws

// after
int cap = Math.max(0, budget - cost);
int r = KnapsackZeroOneTabulation.compute(values, weights, cap, count);

if (capacity < 0) {
    throw new IllegalArgumentException("Capacity must be >= 0");
}
int r = KnapsackZeroOneTabulation.compute(values, weights, capacity, itemCount);

static boolean isValidCapacity(int cap) {
    return cap >= 0;
}

When it happens

Trigger: Calling compute with capacity < 0 — from subtraction that underflows, an uninitialized -1 sentinel, or user input parsed without clamping.

Common situations: Using -1 as a 'not yet set' sentinel for capacity; capacity = budget - cost where cost > budget; deserializing a negative capacity from malformed config.

Related errors

• Weight capacity should not be negative.
• Weights and values must be non-null and of the same length.
• Weights must be positive.
• Input arrays cannot be null.
• Value and weight arrays must be of the same length.

AI-assisted analysis of TheAlgorithms/Java@fdfb9a395b (2026-08-13). Data as JSON: /api/errors/a357dec972344393. Report an issue: GitHub.