Knapsack problem is a NP – complete combinatorial optimization problem. The problem can be described as: given a group of items, each item has its own weight and price. Within the limited total weight, how can we choose to make the total price of the item the highest?

The problem

Suppose there are 5 treasures in the cave a,b,c,d,e (not 5 treasures), their weights are 2,2,6,5,4, and their values are 6,3,5,4,6. Now I give you a backpack with a weight of 10, how to pack the backpack, can you take away the most wealth.

Dynamic programming

Transformation equation

A key step of dynamic programming is to obtain the state transformation equation, the value of the object is expressed by V (k), the weight is expressed by W (k), f[I, j] represents the maximum value of putting the first I objects into the backpack with capacity J, then:

Solving method

Dynamic programming has two equivalent implementation methods:

1. Top down with a memo. This approach writes the procedure recursively in a natural way, but saves the solution to each subproblem (usually in an array or hash table). When a solution to a subproblem is needed, the procedure first checks to see if the solution has already been saved. If so, the saved value is returned directly, saving time; Otherwise, the subproblem is computed in the usual way.

2. Bottom-up method. This approach generally requires the proper definition of the concept of “size” of the subproblem, so that the solution of any subproblem depends only on the solution of the “smaller” subproblem. So we can sort the subproblems in order of size and solve them in order of size from smallest to largest. When a subproblem is solved, the smaller subproblems on which it depends are solved and the results are saved.

Top down approach with cheat sheets

Here is a top-down implementation with a cheat sheet:

var v = [6.3.5.4.6]
var w = [2.2.6.5.4]
var c = 10

function bag (v, w, c) {
  function _bag (v, w, c, f, s) {
    // The size of the subproblem
    var n = v.length
    // The subproblem has been solved
    if (f[n][c] > 0) {
      return f[n][c]
    }
    // Select one item from the remaining items
    for (var i = 0; i < n; i++) {
      var newW = w.slice()
      newW.splice(i, 1)
      var newV = v.slice()
      newV.splice(i, 1)
      // If the weight of the selected item is greater than the remaining capacity of the backpack, the solution to the subproblem is 0
      if (w[i] > c) {
        return 0
      }
      // Otherwise, recursively solve the subproblem to get the largest solution and the currently selected item
      var maxValue = v[i] + _bag(newV, newW, c - w[i], f, s)
      if (f[n][c] < maxValue) {
        f[n][c] = maxValue
        s[n][c] = {v: v[i], w: w[i]}
      }
    }
    // Returns the maximum solution of the subproblem
    return f[n][c]
  }

  var n = v.length
  // Record the maximum value
  var f = []
  // Record the choices made at each step
  var s = []
  for (var i = 0; i <= n; i++) {
    f[i] = []
    s[i] = []
    for (var j = 0; j <= c; j++) {
      f[i][j] = 0
      s[i][j] = null
    }
  }
  _bag(v, w, c, f, s)

  // Prints two two-dimensional arrays
  console.log(f)
  console.log(s)

  // Get the selected item from s
  var selected = []
  var i = n
  var j = c
  var sum = 0
  do {
    var thing = s[i][j]
    if (thing) {
      selected.push(thing)
      j -= thing.w
      i--
    }
  } while (thing)

  return {
    maxV: f[n][c],
    selected: selected
  }
}
Copy the code

instructions

F ends with the following line, where the first line can be ignored, just so that the array index starts at 1, consistent with the formula above:

0	1	2	3	4	5	6	7	8	9	10
null	null	null	null	null	null	null	null	null	null	null
null	null	null	null	null	null	null	null	null	null	null
0	0	0	null	null	null	null	null	null	null	null
0	0	0	0	0	null	6	null	null	null	null
null	null	null	null	6	6	6	null	9	null	null
null	null	null	null	null	null	null	null	null	null	15

Where, f[5][10] is the maximum value obtained in the end, namely 15. You can also see from the above table which problems are recursively solved, i.e. those in the above table that are not null. And if you need to know the last item, you also need to use S:

0	1	2	3	4	5	6	7	8	9	10
null	null	null	null	null	null	null	null	null	null	null
null	null	null	null	null	null	null	null	null	null	null
null	null	null	null	null	null	null	null	null	null	null
null	null	{ v: 3, w: 2 }	{ v: 3, w: 2 }	{ v: 3, w: 2 }	null	{ v: 6, w: 4 }	null	null	null	null
null	null	null	null	{ v: 6, w: 4 }	{ v: 6, w: 4 }	{ v: 6, w: 2 }	null	{ v: 3, w: 2 }	null	null
null	null	null	null	null	null	null	null	null	null	{ v: 6, w: 2 }

Where, s[I][j] represents the first item selected when the previous I objects are put into a backpack of capacity J

Now, let’s go through the process:

1. s[5][10]Indicates that the first 5 items are placed in the backpack with capacity 10 and items are selected{ v: 6, w: 2 }
2. Next we deal with the subproblemss[4][8], selected the item{ v: 6, w: 4 }
3. Next we deal with the subproblemss[3][4], selected the item{ v: 3, w: 2 }
4. Next we deal with the subproblemss[2][2]“, without selecting any items.
5. Get the final selected item as{ v: 6, w: 2 }.{ v: 6, w: 4 }.{ v: 3, w: 2 }

Bottom-up method

Here is the implementation of the bottom-up method:

function bag2 (v, w, c) {
  var f = []
  var s = []
  var n = v.length

  for (var i = 0; i <= n; i++) {
    f[i] = []
    s[i] = []
    for (var j = 0; j <= c; j++) {
      f[i][j] = 0
      s[i][j] = 0}}// Walk through the items
  for (var i = 1; i <= n; i++) {
    var index = i - 1
    // Iterate over the capacity
    for (var j = 0; j <= c; j++) {
      // The status of the current item
      if (w[index] <= j && v[index] + f[i - 1][j - w[index]] > f[i - 1][j]) {
        f[i][j] = v[index] + f[i - 1][j - w[index]]
        s[i][j] = 1
      }
      // The current item is not in
      else {
        f[i][j] = f[i - 1][j]
      }
    }
  }

  return{
    f: f,
    s: s
  }
}
Copy the code

instructions

First, notice the fact that the order in which things are put doesn’t affect our final result. Here we examine whether each item fits in each capacity in the order described in the question.

We still use f for maximum and S for selection.

However, s[I][j] only needs to indicate whether the current item is in, so s[I][j] can be 0 or 1.

F is as follows:

v	w	0	1	2	3	4	5	6	7	8	9	10
–	–	0	0	0	0	0	0	0	0	0	0	0
6	2	0	0	6	6	6	6	6	6	6	6	6
3	2	0	0	6	6	9	9	9	9	9	9	9
5	6	0	0	6	6	9	9	9	9	11	11	14
4	5	0	0	6	6	9	9	9	10	11	13	14
6	4	0	0	6	6	9	9	12	12	15	15	15

S is as follows:

v	w	0	1	2	3	4	5	6	7	8	9	10
–	–	0	0	0	0	0	0	0	0	0	0	0
6	2	0	0	1	1	1	1	1	1	1	1	1
3	2	0	0	0	0	1	1	1	1	1	1	1
5	6	0	0	0	0	0	0	0	0	1	1	1
4	5	0	0	0	0	0	0	0	1	0	1	0
6	4	0	0	0	0	0	0	1	1	1	1	1

Again, we can work backwards to derive the final choice:

1. s[5][10]Is 1, the object is put into the bag
2. inspections[4][6]Is 0, indicating that the object is not placed
3. inspections[3][6], is 0, do not add
4. inspections[2][6], is 1, put
5. inspections[1][4], is 1, put
6. Get the final selected item as{ v: 6, w: 2 }.{ v: 3, w: 2 }.{ v: 6, w: 4 }

conclusion

In the future, problems related to dynamic programming can be solved by using this idea. The key is to construct the transfer function model. Personally, THE top-down approach is easier to understand, but the code is a bit wordy.