背包问题

Given n items with size A_i, 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));

知识共享署名4.0国际许可协议,转载请保留出处; 部分内容来自网络,若有侵权请联系我：前端学堂 » 背包问题