背包问题

题目 #

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]);

解法1 #

代码：

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));

解法2 #

换个思路，也可以看下面的代码 思路：

• 一个一个放物品，直到放不下时；
• 用下一个物品置换现有的物品，需满足条件：
  • 置换后大小小于背包大小
  • 挨个置换，找到最大的可置换的物品；
• 重复上一步；

let things = [3, 4, 7, 5];
let bagsize = 10;
// 计算数组包大小
function size(arr){
	return arr.reduce((a, b) => {return a + b}, 0);
}

function maxPack(maxsize, thingsArr) {
 let res = thingsArr.reduce((a,b)=>{
   	if(size(a) + b < maxsize ){
    	a.push(b)
      	return a; 
    }else{
      	let substi = -1;
      	let tempSize = size(a);
    	a.forEach((item, index)=>{
            // 替换后的数据
            let temp = [...a];
          	temp.splice(index,1,b);
            
        	if(size(temp) >= tempSize && size(temp) <= maxsize ){
              tempSize = size(temp);
              substi = index;
            }
        });
      	if(substi >= 0){
      		a[substi] = b;
        }
        return a; 
    }
 },[]);
 return size(res);
}

console.log(maxPack(bagsize, things));