What is the backpack problem?

Suppose there are now five items [a,b,c,d,e], each of which has a different weight (KG) of [3,4,1,8,4] and a different value of [1,2,3,4,5].

Now Xiao Ming is using a backpack that can hold 12KG. He wants to take away the most valuable items. What is the maximum value that he can take away? What items do you take away?

Note: Each item is limited to one

Greedy algorithms don’t work

The easiest way to think about it:

  1. Weight larger than the backpack is not considered, because it can not fit
  2. If the weight is large and the value is small, it is not considered because the value is not high

Do you just pick the ones with the most value/weight? (Also known as greedy algorithm, each time to choose the current best)

Let’s take an example: Suppose there are 5 items, N = 5, and the backpack capacity is 100. The quality and value of each item are as follows:

  • value/weight = 20/20 = 1
  • value/weight = 30/30 = 1
  • Value /weight = 44/40 = 1.1
  • Value /weight = 55/50 = 11.1
  • value/weight = 60/60 = 1

If according to the above strategy: priority to choose the “price to quality ratio” is the largest: (the third + the fourth) at this time quality: 40+50=90 value: 44+55 =99

The actual better selection strategy is: (the first + the second + the fourth) at this time quality: 20+30+50=100 value: 20+30+55=105 although 1,2 high quality ratio is not the highest, but 1,2, 4 can fill the whole backpack, that is, the best combination

Therefore, the greedy strategy of “price/quality ratio” is obviously not the optimal strategy.

The reason is: this problem contains two levels of optimality, 1 is the highest value/weight ratio and 2 is the best combination because this algorithm only satisfies the high price/quality ratio, not the best combination

Dynamic programming works

Dp [I][j] is a two-dimensional array 0<= I <=N, 0<=j<=C whose dp table is (N+1)x(C+1) dimension

State transition equation

  1. If w[I] > J, dp[I] = DP [I][J];
  2. If w[I] <= j, then there are two considerations for the ith item 2.1. 2.2. If put in backpack, the value is i-1 item put in J-W [I] backpack + I item put in dp[I][j] = dp[i-1][J-W [I]] + v[I]; 2.3. To play or not to play? Depends on the value of which is greater, that is, dp [I] [j] = Max (dp [j], [I – 1] dp [I – 1] [j w. [I]] + v [I])

Note:

  • Each item has only 1, item I either does not put (0) or (1), which is the 01 knapsack problem

  • The core of this algorithm is: from the bottom up, the current value is calculated from the previous known value

Diagram analysis of status transfer process

Vertical: represents item I. Horizontal: represents backpack space J

Horizontal items are 0, i.e. there are no items, and the backpack is worth 0 no matter how big the space is

The longitudinal backpack has zero space, that is, the backpack can’t hold any items, and the value is zero

Longitudinal backpack space 1

Longitudinal backpack space 2

In the same way, the remaining longitudinal packs are 3-12

Think: What are the items in the backpack? From I = 5, j = 12 cell, dp [5] [12] – > dp [4] [8] (not to put, discarded) – > dp [3] [8] – > dp [2], [7] – > dp [1], [3] know backpack to put items 4,3,2,1 totaling 5 + 3 + 2 + 1 = 11

Js implementation

function packBag(N, C, w, v){
    // Create a two-dimensional array (N+1) * (C+1)
    let dp = new Array(N+1); / / N + 1
    for(let z = 0; z <= N; z++){/ / C + 1 column
        dp[z] = new Array(C+1);    
    }
    // initialize row 0 and column 0 with initial values of 0
    for(let z=0; z<=C; z++){
        dp[0][z] = 0;
    }
    for(let z=0; z<=N; z++){
        dp[z][0] = 0;
    }
    // Select * from rows 1 to N to 1 to C
    for(let j=1; j<=C; j++){
        for(let i=1; i<=N; i++){let notPackValue = dp[i-1][j];
            if(w[i] > j){ / / not put
                dp[i][j] = notPackValue;                
            }else{
                let packValue = dp[i-1][j-w[i]] + v[i];
                dp[i][j] = Math.max(notPackValue,packValue); }}}console.log(`dp:`,dp);
    return dp[N][C];
}
module.exports = {
    packBag : packBag
};
Copy the code

Test data {N: 5, C: 12, w:,3,4,1,8,4 [0], v:,1,2,3,4,5 [0]}

The results

dp: [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] to [0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [0, 0, 0, 1, 2, 2, 2, 3, 3, 3, 3, 3, 3], [0, 3, 3, 3, 4, 5, 5, 5, 6, 6, 6, 6, 6], [0, 3, 3, 3, 4, 5, 5, 5, 6, 7, 7, 7, 8], [0, 3, 3, 3, 5, 8, 8, 8, 9, 10, 10, 10, 11 ] ] result: 11Copy the code