01背包问题的js解决方式_背包算法java

如果你有兴趣看这个相信你已经对背包问题有所了解，所以关于背包问题的描述，我就不写了。

只记录一下自己对这个问题的一些看法和思考，于我而言，这个东西现在困扰我的是如何确定最优解。

实质上关于背包问题网上的东西我大体都有看过，对于这个问题，常见的就是使背包重量动态增长，然后遍历每个要装入的这些包裹，当包裹的重量小于等于当前背包的重量时，就可以装进背包了，那应不应该把当前这个包裹装入呢，这取决于 装入这个包裹，和未装入这个包裹的时候哪个状态的背包的价值最大，所以，背包问题的关键是‘01’，要么装，要么不装。

然后问题来了，未装入这个包裹的时候，这个时候的背包的最大的价值在哪里呢？

首先，在背包重量逐渐增大至与最小包裹相等的时候，这个时候就出现了第一个最优解（背包里物品最大值），因为在他前边这个背包里是没有任何东西的，我们需要把它保存下来，怎么保存呢？以当前背包的重量为行标，当前包裹的序列为列标将其存到一个二维数组里，这样做了之后，在决定要不要将当前包裹扔进背包的时候，可以比较一下装进这个包裹和不装这个包裹时候背包的最优解，保存结果的那个二维数组行标减去当前包裹的重量，and列标减一 就是 当前包裹的前几个包裹扔进这个背包能获得的最优解，而有一个数学关系是始终成立的，就是： 当前背包的重量 - 当前包裹的重量 这个差值 确定的行标，如果该行存在，那么这个行数是 >= 0 的， 所以 当前背包的重量 >= 当前包裹的重量，这也就确定了我们现在的背包是可以装的下我们正在遍历的包裹的。

写一段试试吧：

/**
     *
     * @param {Array} items 包裹尺寸集
     * @param {Array} values包裹价值集
     * @param {number} bagSize 背包尺寸
     * @return {Array} 返回遍历后的数组，最优解在该数组的最后一个元素上
     */
function mostPrecious( items,values,bagSize ){
    let result = [];
    for( let size = 0 ; size <= bagSize; size++){
        result[size] = [];
        for( let item = 0; item < items.length; item++ ){
            if( size == 0 ){//背包尺寸为0装不下任何东西
                result[size][item] = 0;
                continue;
            }
             if( size - items[item] < 0 ){//当前重量的背包无法装下当前包裹，那么最优解的值就是前一个包裹能装进去的价值
                 result[size][item] = result[size][item-1] || 0;
                 continue;
             }
            if( size - items[item] >= 0 )
            {
              result[size][item] = Math.max( (result[ size - items[item] ][item-1]|| 0) + values[item],result[size][item-1] || 0 )
            }
        }
    }
    return result;
}

今天先写到这儿 bug 不断啊。。。

明天再改 --- debug 2017-12-14---------

明天记录一下改bug中的心得，现在这个算法已经ok了

貌似没问题了 ---debug 2017-12-14 晚上-------

后记

回答一下开头提出的问题，为什么这么做就能确定最优解呢？

因为背包重量是由零开始动态增长的，这样保证了，当背包重量与包裹里最小的重量相等的时候，结果集所确定的第一个结果的绝对正确性，往后背包重量继续增长的时候，确定当前包裹是否要加入背包时所参考的前一个的最优解值总是正确的，也就保证了整个算法的正确性。

最后就是：决定要不要加入当前这个包，取决于，加入这个包之前的包裹能确定的最优解，加上这个包的value 和没加入这个包之前的背包的最优解谁更大。