Knapsack problem is the most classic example of dynamic programming. Backpack problem is divided into 01 backpack, backpack, multiple backpack, etc., the interview is a common 01 backpack problem and complete backpack problem.

In our development interviews, the two most common backpack questions are 01 backpack and full backpack. So in this article we derive plus implementation plus optimization of these two knapsack problems.

0/1 knapsack problem

Let’s take a look at 01 Backpack problem:

There are N items and a backpack with a maximum weight of W. The ith item's weight is weight[I] and the resulting value is value[I]. Each item can only be used once to figure out which items to put into the backpack with the maximum sum of itemsCopy the code

Let’s start with a set of use cases:

W = 10 N = 4 wights =,3,4,7 [2] values =,3,5,9 [1]Copy the code

First of all, we analyze dp[I][J] of dynamic programming. We first use two-dimensional array to represent it, which can be more clear. Its meaning is to take the maximum sum of the sum of the value of the items in 0-I items and put it into the backpack with capacity J.

I is the number of things we have and J is the size of our backpacks. With that in mind, let’s look at the chart below.

We can find that our element is always determined by the element above it and by dp[i-1][j-wights [I-1]] + values[i-1].

And we should start at zero when we initialize.

Then we can easily write js code:

  function PackageTest(M, N, wights, values) {
    let dp = new Array(N + 1).fill(0).map(() = > new Array(M + 1).fill(0))
    for (let i = 1; i <= N; i++) {
      for (let j = 1; j <= M; j++) {
        if (j < wights[i - 1]) {
          dp[i][j] = dp[i - 1][j]
        } else {
          dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - wights[i - 1]] + values[i - 1])}}}console.log(dp)
    return dp[N][M]
  }
Copy the code

Optimization of scrolling arrays:

This method is to our two dimensional array to a one-dimensional array, how will be reduced to a two-dimensional array dimension, we can observe the data above, we will find that we always rely on a line of data, so we can abandon the row data, directly in a line on the basis of calculation, but it is important to note that We need to rely on data that precedes the current position of the element in our previous layer, so we can’t go through the array sequentially because that would change the dp[j-wights [i-1]] values we need. So we’re going to go in reverse order.

So we can write Js code:

 function PackageTestTwo(M, N, wights, values) {
    let dp = new Array(M + 1).fill(0)
    for (let i = 1; i <= N; i++) {
      for (let j = M; j >= 1; j--) {
        if (j >= wights[i - 1]) {
          dp[j] = Math.max(dp[j], dp[j - wights[i - 1]] + values[i - 1])}}}}Copy the code

Above is 01 knapsack solution process. I prefer the second way to scroll through the data because it’s more efficient, but understanding the second way is based on understanding the first solution.

Complete knapsack problem

Topic:

There are N items and a backpack of capacity V, with an infinite number of items for each item. Item I has volume VI and value WI. Solve which items to put into the backpack so that the total volume of these items does not exceed the backpack capacity, and the total value of the maximum. Output maximum value.Copy the code

We find the following analysis and 01 backpack difference is that a commodity can appear many times, and 01 backpack can only appear once. So after the goal is clear, we continue to type to determine the way of moving gauge.

First of all, we still choose DP [I][J], which has the same meaning as dp of 01 backpack.

Derive the following:

We find that, unlike 01, our current element depends on the element at the same position in the previous layer and the rest of the pack element in the row.

So we establish the recurrence formula as written above.

Finally write the JavaScript code:

  function PerfectPacage(M, N, wights, values) {
    let dp = new Array(N + 1).fill(0).map(() = > new Array(M + 1).fill(0))
    for (let i = 1; i <= N; i++) {
      for (let j = 1; j <= M; j++) {
        if (j < wights[i - 1]) {
          dp[i][j] = dp[i - 1][j]
        } else {
          dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - wights[i - 1]] + values[i - 1])}}}return dp[N][M]
  }
Copy the code

Scrollarray optimization:

Like 01, we’re still going to reduce two dimensions to one. But the difference is that instead of relying on the data from the previous layer, we use the data from the rest of the layer, so we rely on the former, and the former depends on the previous element, so we use sequential traversal.

If we were to iterate through a one-dimensional array, the data would have been changed, and the elements in the previous group would have disappeared as soon as we started the loop.

Max (dp[j], dp[j-wights [i-1]] + values[i-1])

Code implementation:

  function PerfectPacage2(M, N, wights, values) {
    let dp = new Array(M + 1).fill(0);
    for (let i = 1; i <= N; i++) {
      for (let j =1; j <= M; j++) {
        if (j >= wights[i - 1]) {
        dp[j] = Math.max(dp[j], dp[j - wights[i - 1]] + values[i - 1])}}console.log(dp)
    }
    return dp[M]
  }
Copy the code

The inner loop starts directly at wight[i-1], because the previous ones are not qualified, or the elements don’t need to be adjusted.

  function PerfectPacage2(M, N, wights, values) {
    let dp = new Array(M + 1).fill(0);
    for (let i = 1; i <= N; i++) {
      for (let j = wights[i - 1]; j <= M; j++) {
        dp[j] = Math.max(dp[j], dp[j - wights[i - 1]] + values[i - 1])}console.log(dp)
    }
    return dp[M]
  }

Copy the code