Given n items with size Ai, an integer m denotes the size of a backpack. How full you can fill this backpack?
Example 1:
Input: [3,4,8,5], backpack size=10
Output: 9
Example 2:
Input: [2,3,5,7], backpack size=12
Output: 12
Challenge
O(n x m) time and O(m) memory.
O(n x m) memory is also acceptable if you do not know how to optimize me
正向求解,比如给定的背包容量是10,那么我先创建10个背包,每个背包的序号就是背包的容量:
🎒0 🎒1 🎒2 🎒3 🎒5 🎒6 🎒7 🎒8 🎒9 🎒10
然后假设有4个物品[3, 4, 7, 5], 假设我先拿出来第一个物品消耗容量为3,那么上面10个背包,每个背包最多存放价值是:
0 0 0 3 3 3 3 3 3 3 3
很明显,容量大于3的都可以放得下,所以能放的最大容量是3.
然后拿出来第2个物品消耗容量为4,那么上面10个背包,每个背包最多存放价值是:
0 0 0 3 4 4 4 7 7 7 7
很明显,容量大于4的是4, 大于或等于7的可以放前面2个物品,价值为7,依次类推。。。
得到一个公司:
buff[j] = Math.max(buff[j], buff[j - things[i]] + things[i]);
代码:
let things = [3, 4, 7, 5]; let bagsize = 10; function maxPack(size, things) { // make buff as a baglist let buff = []; // init each bag with 0 value, the index as the bag size for (let eachSize = 0; eachSize <= size; eachSize++) { buff[eachSize] = 0; } // loop each thing for (let i = 0; i < things.length; i++) { // when i=0, compute each bag's max value with each size // and so forth for (let j = size; j >= things[i]; j--) { buff[j] = Math.max(buff[j], buff[j - things[i]] + things[i]); } console.log(...buff); } return buff[size]; } console.log(maxPack(bagsize, things));