背包问题---01背包

<script>

    /*
    * 背包问题：
    *   从M件物品中取出若干个放在容积为W的背包中，
    *   已知每件物品的体重是 w1,w2,...,wn
    *   已知每件物品的价值是 p1,p2,...,pn
    *   如何装物品，实现最大价值？？
    *
    * 类型：分为01背包和部分背包
    *   01背包：指背包中的物体是不可分割的，如手机，相机，解决方案---动态规划方案
    *
    *   部分背包：指背包中的物体可以分割，如大米，水，解决方案---贪心算法
    *
    *
    * */
    let M = 5;
    let W = 16;
    let arrP = [4,5,10,11,13];
    let arrW = [3,4,7,8,9];


    /*
     * 动态规划背包---求最大值：
     *   M --- 一共有多少件物品
     *   W --- 背包的最大承载量
     *   arrW --- 每件物品的重量
     *   arrP --- 每件物品的价值
     *
     * 推荐看看：原理推算
     * 当  没有物品的时候
     * arrP=[]
     * arrW=[]
     * W = 16           0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
     *
     * 当  1件物品的时候
     * arrP=[4]               3
     * arrW=[3]         0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
     * W = 16           0 0 0 4 4 4 4 4 4 4 4 4 4 4 4 4 4
     *
     *
     * 当  2件物品的时候
     * arrP=[4,5]             3 4     7
     * arrW=[3,4]       0 0 0 4 4 4 4 4 4 4 4 4 4 4 4 4 4
     * W = 16           0 0 0 4 5 5 5 9 9 9 9 9 9 9 9 9 9
     *
     * 当  3件物品的时候
     * arrP=[4,5,10]          3       7     10
     * arrW=[3,4,7]     0 0 0 4 5 5 5 9 9 9 9  9  9  9  9  9  9
     * W = 16           0 0 0 4 5 5 5 9 9 9 10 15 15 15 19 19 19
     * */
    function plan(M, W, arrW, arrP) {
        // 遍历物品总数量---按照物品的个数依次进行动态规划
        // 存放动态规划的结果数组
        let result = [];
        for ( var i = 0; i <= M; i++ ) {
            result[i] = [];
            // 遍历背包的总承载力
            for ( var j = 0; j <= W; j++ ) {
                // 当背包里没有物品的时候
                if ( i === 0 ) {
                    result[i][j] = 0;
                }
                // 当 arrW[i - 1] > j 的时候，本次结果直接等于上一次的结果
                else if ( arrW[i - 1] > j) {
                    result[i][j] = result[i - 1][j];
                }
                // 当 arrW[i - 1] < j 的时候
                // 总的价值 = Math.max(本次物品的价值 + 上一次物品的价值, 上一次比较的价值)
                else {
                    result[i][j] = Math.max(arrP[i - 1] + result[i - 1][j - arrW[i - 1]], result[i-1][j]);
                }
            }
        }
        // 最后一个就是最大值
        return result[i-1][j-1];
    }
    console.log(plan(M, W, arrW, arrP));

</script>