/**
* 某旅行者外出, 需要将5件物品装入包中. 包的总容量是10kg, 物品重量及价值如表. 问如何装这些物品, 才能使得总价值最大?
* A B C D E
* 4 5 6 2 2
* 6 4 5 3 6
*/

function calc(n, m, w, v){
    w.unshift(0);
    v.unshift(0);
    let s = [...Array(n + 1)].map(x=>[...Array(m + 1)].map(()=>0));
    for (let i = 0; i <= n; i++) {
        for (let j = 0; j <= m; j++) {
            if (i === 0 || j === 0){
                s[i][j] = 0;
            }
            else if (j - w[i] < 0) {
                s[i][j] = s[i - 1][j];
            }
            else {
                s[i][j] = Math.max(s[i - 1][j], s[i - 1][j - w[i]] + v[i]);
            }
        }
    }
    return s[n][m];
}

let maxValue = calc(5, 10, [4,5,6,2,2], [6,4,5,3,6]);
console.info(maxValue);