ナップザック問題をDPテーブルで解くやつ

ナップザック問題をDPテーブルで解くやつ.ts

/*
 * n 個の 0 を格納する配列を返します
 */
const initArray = (n: number) => (new Array(n)).fill(0)

const items = [[2,3],[1,2],[3,6],[2,1],[1,3],[5,85]].map(item => ({
    weight: item[0],
    value: item[1],
}))

const W = 9

const dpTable = initArray(items.length + 1).map(i => initArray(W + 1))

initArray(items.length).forEach((_, i) => {
    initArray(W + 1).forEach((_, w) => {
        const item = items[i]

        // NOTE: item を採用する場合 ↘
        const withTheItem = (() => {
            if (w - item.weight < 0) {
                return 0
            }
            return dpTable[i][w - item.weight] + item.value
        })()

        // NOTE: item を採用しない場合 ↓
        const withoutTheItem = (() => {
            return dpTable[i][w]
        })()

        // NOTE: max(withTheItem, withoutTheItem)
        dpTable[i + 1][w] = withTheItem > withoutTheItem ? withTheItem : withoutTheItem
    })
})

console.table(dpTable)