背包问题--部分背包

<script>

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

    /*
     * 动态规划背包---求最大值：
     *   M --- 一共有多少件物品
     *   W --- 背包的最大承载量
     *   arrW --- 每件物品的重量
     *   arrP --- 每件物品的价值
     *
     * 原理：根据比例来
     * r : arrP[i] / arrW[i]
     * 然后进行排序，依次添加
     * 如果arrW[i] < W，可拆分
     *
     * */
    function plan(M, W, arrW, arrP) {
        var result = 0;
        var newArr = [];
        // 计算比例，创建新数组
        for ( var i = 0; i < M; i++ ) {
           newArr.push({
               w : arrW[i],
               p : arrP[i],
               r : arrP[i] / arrW[i]
           });
        }
        // 按照比例排序(降序)，一遍装包操作
        newArr.sort(function (obj1, obj2) {
            return obj2.r - obj1.r;
        });
        // 依次按照比例大小开始装包
        for( var i = 0; i < newArr.length; i++ ) {
            if( newArr[i].w <= W ) {
                result += newArr[i].p;
                W -= newArr[i].w;
                //console.log(result, '', W);
            }
            // 开始拆分装包
            else {
                result += W / newArr[i].w * newArr[i].p;
                break;
            }
        }
        return result.toFixed(2);
    }
    console.log(plan(M, W, arrW, arrP));

</script>