如果你有兴趣看这个相信你已经对背包问题有所了解，所以关于背包问题的描述，我就不写了。
只记录一下自己对这个问题的一些看法和思考，于我而言，这个东西现在困扰我的是如何确定最优解。
实质上关于背包问题网上的东西我大体都有看过，对于这个问题多重背包问题，常见的就是使背包重量动态增长，然后遍历每个要装入的这些包裹，当包裹的重量小于等于当前背包的重量时，就可以装进背包了，那应不应该把当前这个包裹装入呢多重背包问题，这取决于 装入这个包裹，和未装入这个包裹的时候哪个状态的背包的价值最大，所以，背包问题的关键是‘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] = Math.max( (result[ size - items[item] ][item-1]|| 0) + values[item],result[size][item-1] || 0 )
}
}
}
return result;
}
今天先写到这儿 bug 不断啊。。。
声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。