0/1 knapsack — maximize value within a weight budget via 2D DP

knapsack.cell

// 0/1 knapsack — maximize value within a weight budget via 2D DP.
// Demonstrates: parallel weight/value lists, a (n+1) x (capacity+1) DP table
// built as nested Lists, the take-or-skip recurrence, and max() of two options.
//
//   soma run  examples/corpus/algorithms/knapsack.cell best 7
//   soma test examples/corpus/algorithms/knapsack.cell

cell Knapsack {
    face {
        signal best(capacity: Int) -> Int
        signal solve(weights: List, values: List, capacity: Int) -> Int
    }

    // fixed instance used by `best` and the tests
    on best(capacity: Int) {
        return solve(list(1, 3, 4, 5), list(1, 4, 5, 7), capacity)
    }

    on solve(weights: List, values: List, capacity: Int) {
        let n = len(weights)
        // dp[i][c] = best value using the first i items with budget c
        let dp = list()
        for i in range(0, n + 1) {
            let row = list()
            for c in range(0, capacity + 1) { row = push(row, 0) }
            dp = push(dp, row)
        }
        for i in range(1, n + 1) {
            let wt = weights[i - 1]
            let val = values[i - 1]
            for c in range(0, capacity + 1) {
                let skip = dp[i - 1][c]
                if wt <= c {
                    let take = dp[i - 1][c - wt] + val
                    dp[i][c] = max(skip, take)
                } else {
                    dp[i][c] = skip
                }
            }
        }
        return dp[n][capacity]
    }
}

cell test KnapsackTests {
    rules {
        assert best(7) == 9
        assert best(0) == 0
        assert best(1) == 1
        assert best(100) == 17
        assert solve(list(2, 2, 2), list(3, 3, 3), 4) == 6
        assert solve(list(5), list(10), 3) == 0
    }
}