Unbounded Knapsack

The problem

Implement `unboundedKnapsackTopDown(weights, values, capacity)`: given `n` item types where type `i` weighs `weights[i]` and is worth `values[i]`, and a bag of the given capacity, return the maximum total value. Unlike 0/1, each type may be taken any number of times.

`weights = [2, 4, 6], values = [5, 11, 13], capacity = 10` returns `24` under 0/1 rules — items `4` and `6`, the only pair that fits — but `27` here: two of the weight-`4` item plus one weight-`2`, for `11 + 11 + 5`. The two answers diverge exactly where repeating the best-ratio item beats diversifying across distinct ones.

The approach

The state is unchanged from the 0/1 table — `memo[i][j]` is still the best value from the first `i` item *types* within capacity `j` — but the meaning of the include branch shifts. Taking item `i` no longer consumes it, so after spending `weights[i-1]` of capacity you're back at the same set of available types, one row unchanged: `values[i-1] + memo[i][j - weights[i-1]]`. The exclude branch still drops to `memo[i-1][j]`, because deciding never to use type `i` really does remove it.

That same-row read is why the recurrence still terminates and still fills in the right order. `j - weights[i-1]` is strictly less than `j` whenever the weight is positive, so the cell being read is always to the left of the cell being written, and the inner loop runs left to right — it's already computed. The dependency points backwards along the row instead of down to the previous one, and tabulation doesn't care which direction as long as it points backwards.

The guard `weights[i-1] <= j` does double duty here. In the 0/1 version it kept `j - weights[i-1]` from going negative; here it also happens to be the only thing standing between the table and a zero-weight item — a zero-weight, positive-value type would make the true answer unbounded, and the cell would be computed from a read of itself. Worth knowing the input assumption is 'weights are strictly positive', not just 'weights are non-negative'.

Both seeding loops stay at `0` and both still say the same thing: no item types available, or no capacity left, means no value. Unlike the counting and minimising variants that follow, nothing about the base cases changes when you go unbounded — repetition is a property of the recurrence, not of the boundary.

A note on the name, same as the 0/1 entry: `unboundedKnapsackTopDown` is bottom-up tabulation. It starts at the base cases and builds toward the answer; top-down would be recursion plus a memo, starting at `memo[n][capacity]` and descending. The code is right and the label is inverted, carried over from the earlier file by copy-paste.

The solution

export function unboundedKnapsackTopDown(weights, values, capacity) {
    const memo = Array.from({ length: weights.length + 1 }, () => Array(capacity + 1).fill(null))

    // initialize the first row with 0
    for (let i = 0; i <= weights.length; i++) {
        memo[i][0] = 0
    }
    // initialize the first column with 0
    for (let j = 0; j <= capacity; j++) {
        memo[0][j] = 0
    }

    // fill the memo table
    for (let i = 1; i <= weights.length; i++) {
        for (let j = 1; j <= capacity; j++) {
            if (weights[i-1] <= j) {
                memo[i][j] = Math.max(values[i-1] + memo[i][j-weights[i-1]], memo[i-1][j])
            } else {
                memo[i][j] = memo[i-1][j]
            }
        }
    }

    // return the maximum value
    return memo[weights.length][capacity]
}

Time O(n * capacity)Space O(n * capacity)