01 backpack problem

knapsack problem

Derived from Random code recording ： Dynamic programming ： About 01 knapsack problem , You should know this ！

01 knapsack

Yes n Items and one can carry a maximum weight of w The backpack . The first i The weight of the item is weight[i], The value is value[i] . Each item can only be used once , Solve which items are loaded into the backpack, and the total value of the items is the largest .

	weight	value
goods 0	1	15
goods 1	3	20
goods 2	4	30

/**
 *
 * @param {*} weight  Item weight 
 * @param {*} value  The value of the goods 
 * @param {*} size  Types of backpacks 
 * @returns
 */
function knapsack(weight, value, size) {

}

1、 Backtracking solution 0-1 knapsack problem

Backtracking is actually an exhaustive process , Enumerate all possible situations , Find the best solution from it , That is, the maximum value that can be loaded into a backpack .

/**
 *
 * @param {*} weight  Item weight 
 * @param {*} value  The value of the goods 
 * @param {*} size  Types of backpacks 
 * @returns
 */
function knapsack(weight, value, size) {
  // 1.  Backtracking solution  0 - 1  knapsack problem 
  let maxValue = Number.MIN_VALUE;

  const backTrack = (i, total, totalValue) => {
    //  The back pack is full   perhaps   All the items have been inspected 
    if (total === size || i === weight.length) {
      if (totalValue > maxValue) {
        maxValue = totalValue;
      }
      return;
    }

    //  Choose not to load items  i
    backTrack(i + 1, total, totalValue);

    if (total + weight[i] <= size) {
      //  Choose to load items  i
      backTrack(i + 1, total + weight[i], totalValue + value[i]);
    }
  };

  backTrack(0, 0, 0);

  return maxValue;
}

knapsack([1, 3, 4], [15, 20, 30], 4); // 35

Time complexity ：O(2^n),n Is the number of items

We can see that the time complexity of the backtracking algorithm is exponential , Quite high , Let's use dynamic programming to solve ！

2、 Dynamic programming solves 0-1 knapsack problem

Using the dynamic programming trilogy ：

1. determine dp Array （dp table） And the meaning of subscripts

dp[i][j]: Indicates that the item is from 0 - i Select any load capacity between the j The biggest value of our backpack

understand dp The meaning of arrays is very important , Don't keep thinking about how much you need to put in your backpack to fill it up , Then find the maximum . The idea of using dynamic programming here is to enumerate all possible states , Horizontal is the object , Vertical is capacity

1. Determine the recurrence formula

   For items i There are only two states , Choose to load the backpack perhaps Do not choose to load the backpack

   ① Do not choose to load the backpack

   If it is not selected, it will be consistent with the previous status , namely

   dp[i][j] = dp[i - 1][j];
   

   ② Choose to load the backpack

   dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
   

   dp[i - 1][j - weight[i]] The capacity of the backpack is j - weight[i] Don't put any objects in the i Maximum value of , that dp[i - 1][j - weight[i]] + value[i] The capacity of the backpack is j - weight[i] Put in the items when i Maximum value of .

   Due to the array index from 0 Start , And in our definition i It's from 1 Start counting , therefore value[i-1] and weight[i-1] It means the first one i The value and weight of an object .

   dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1]);
   

2. dp How to initialize an array

   Here we are creating dp Initializes all elements of the array to 0, Follow up During the iteration, the items are changed from i = 1 Start

3. Determine the traversal order

   You can traverse items or backpack capacity , Because the evaluation here is based on An element in the upper left corner is iterated , The traversal order does not affect the result

4. Give an example to deduce dp Array

   console.table(dp);

/**
 *
 * @param {*} weight  Item weight 
 * @param {*} value  The value of the goods 
 * @param {*} size  Types of backpacks 
 * @returns
 */
function knapsack(weight, value, size) {
  const length = weight.length;
  let dp = new Array(length + 1).fill().map(() => new Array(size + 1).fill(0));

  for (let i = 1; i <= length; i++) {
    for (let j = 0; j <= size; j++) {
      if (weight[i - 1] <= j) {
        //  Due to the array index from  0  Start , And in our definition  i  It's from  1  Start counting ,
				//  therefore  value[i-1]  and  weight[i-1]  It means the first one  i  The value and weight of an object .
        dp[i][j] = Math.max(
          dp[i - 1][j],
          dp[i - 1][j - weight[i - 1]] + value[i - 1]
        );
      } else {
				//  The capacity of the item is greater than that of the backpack , can't let go 
        dp[i][j] = dp[i - 1][j];
      }
    }
  }

  console.table(dp);

  return dp[length][size];
}

dp The array is printed as follows ：

┌─────────┬───┬────┬────┬────┬────┐
│ (index) │ 0 │ 1  │ 2  │ 3  │ 4  │
├─────────┼───┼────┼────┼────┼────┤
│    0    │ 0 │ 0  │ 0  │ 0  │ 0  │
│    1    │ 0 │ 15 │ 15 │ 15 │ 15 │
│    2    │ 0 │ 15 │ 15 │ 20 │ 35 │
│    3    │ 0 │ 15 │ 15 │ 20 │ 35 │
└─────────┴───┴────┴────┴────┴────┘

3、 The two-dimensional optimization of dynamic programming is one-dimensional （ Scrolling array ）

Using the dynamic programming trilogy ：

1. determine dp Array （dp table） And the meaning of subscripts

   dp[j]: Capacity of j The backpack , The value of the items carried can be up to dp[j]

2. Determine the recurrence formula

   dp[j - weight[i]] The capacity is j - weight[i] The maximum value of your backpack .

   dp[j - weight[i]] + value[i] The capacity is j - goods i weight The backpack add goods i The value of .（ That is, the capacity is j The backpack , Put something in i After that, the value is ：dp[j]）

   dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
   

3. A one-dimensional dp How to initialize an array

   dp[j] Express ： Capacity of j The backpack , The value of the items carried can be up to dp[j], that dp[0] It should be 0, Because the backpack has a capacity of 0 The greatest value of the items carried is 0.

4. A one-dimensional dp Array traversal order

     //  Traverse the items 
     for (let i = 0; i < weight.length; i++) {
       //  Then traverse the backpack capacity in reverse order 
       for (let j = size; j >= weight[i]; j--) {
         
       }
     }
   

   If positive order traverses

   dp[1] = dp[1 - weight[0]] + value[0] = 15
   
   dp[2] = dp[2 - weight[0]] + value[0] = 30
   

   here dp[2] It's already 30 了 , It means things 0, It was put in twice , So you can't traverse in positive order .

   Why traverse in reverse order , You can ensure that the items are only put in once ？

   The reverse order is to calculate first dp[2]

   dp[2] = dp[2 - weight[0]] + value[0] = 15 （dp The array has been initialized to 0）
   
   dp[1] = dp[1 - weight[0]] + value[0] = 15
   

   So cycle back and forth , Each acquisition state will not coincide with the previous acquisition state , So each item can only be taken once .

   First traverse the nested items and traverse the backpack capacity , Can you traverse the backpack capacity and nested items first ？

   Can not be ！

   Because one dimension dp Writing , Backpack capacity must be traversed in reverse order （ The reason has been mentioned above ）, If the traversal backpack capacity is placed on the upper layer , Then each dp[j] Only one item will be put in , namely ： There is only one item in the backpack .

   （ If you can't read here , Just think back dp[j] The definition of , Or just two for Try reversing the cycle order ！）

   So one dimension dp The knapsack of array is actually very different from two-dimensional in traversal order ！

/** * * @param {*} weight  Item weight  * @param {*} value  The value of the goods  * @param {*} size  Types of backpacks  * @returns */
function knapsack(weight, value, size) {
    
  let dp = new Array(size + 1).fill(0);

  //  Traverse the items 
  for (let i = 0; i < weight.length; i++) {
    
    //  Then traverse the backpack capacity in reverse order 
    for (let j = size; j >= weight[i]; j--) {
    
      dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
    }
  }

  return dp[size];
}