【JavaScript】ナップザック問題

前回の続き．ナップザック問題をJavaScriptで実装してみたメモ．

knapsack.js

const generate2DArray = (height, width) => {
    return [...Array(height)].map(() => Array(width).fill(0));
}

const knapsack = (items, weightLimit) => {
    const listHeight = items.length;
    let dp = generate2DArray(listHeight + 1, weightLimit + 1); // 0行目・0列目を含む二次元配列を生成

    for (let col = 0; col < listHeight; col++) {
        for (let row = 0; row < weightLimit + 1; row++) {
            if (row >= items[col][0]) {
                dp[col + 1][row] = Math.max(dp[col][row], dp[col][row - items[col][0]] + items[col][1]);
            } else {
                dp[col + 1][row] = dp[col][row];
            }
        }
    }

    return dp[listHeight][weightLimit];
}

const items = [
    [2, 3],
    [1, 2],
    [3, 6],
    [2, 1],
    [1, 3],
    [5, 85]
]; // weight, value

console.log(knapsack(items, 9)); // 94