01背包

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 计算01背包问题的结果
 * @param V int整型 背包的体积
 * @param n int整型 物品的个数
 * @param vw int整型二维数组 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi
 * @return int整型
 */
function knapsack(V, n, vw) {
    // write code here
    const val = Array.from({ length: V + 1 }).map(() =>
        new Array(n + 1).fill(0)
    );

    Array.from({ length: V + 1 }).forEach((_, volumn) => {
        Array.from({ length: n + 1 }).forEach((_, count) => {
            if (!volumn || !count) return;
            const [objVolumn, objWeight] = vw[count - 1];
            if (volumn - objVolumn >= 0) {
                val[volumn][count] = Math.max(
                    val[volumn][count - 1],
                    val[volumn - objVolumn][count - 1] + objWeight
                );
            } else {
                val[volumn][count] = val[volumn][count - 1];
            }
        });
    });

    return val[V][n];
}
module.exports = {
    knapsack: knapsack,
};