Front end algorithm – knapsack problem

Recently brush LeetCode found a daily problem in recent days, backpack problem is still quite a lot, the following I will according to their own views on the solution, make some summary.

preface

So let’s say I have a backpack with a capacity of 10

If there are items, calculate, with the capacity of 10 backpack, how to pack the items inside the backpack, the value of the sum of the maximum.

items The size of the The value of
apple 3 5
banana 3 3
pears 2 6
durian 4 7
pineapple 5 8

The way to think about it is that when we pack fruit one by one in a backpack, the first thing we pack is apples.

So capacity is 10, apples are worth 5, and size is 3, so we’re left with 10 minus 3, which is 7.

So we know that if we put apples in the bag then the maximum value of our backpack right now is equal to the maximum value of the backpack at 7 times plus the value of the apples.

The backpack capacity is the maximum value of 7 days, specifically refers to the fruit in order, before the apples, the maximum value of 7 days. And then if we keep pushing up, we get a two-dimensional array dp.

Item size 0 1 2 3 4 5 6 7 8 9 10
0 0 0 0 0 0 0 0 0 0 0 0
3 (Apple-5) 0 0 0 5 5 5 5 5 5 5 5
3 (banana -3) 0 0 0 5 5 5 8 8 8 8 8
2 (Pear -6) — — — — — — — — — — —
4 (Durian -7) — — — — — — — — — — —
5 (Pineapple-8) — — — — — — — — — — —

We insert the backpack into [0-10] different backpack, and then let the fruit in turn into these different backpack, we first look at the apple, because the size of the apple is 3, so the backpack capacity of 0-2 can be loaded into the value of 0, after 3, can be loaded into the apple, so the value is 5.

When began to load a banana, similarly 2-0, pack, are 0 to 3, we load the bananas, capacity surplus 0, before loading apples, capacity of 0, can load the maximum value of 0, namely dp [0] [0], at this time we load value for 3, but we can find that the capacity of 3, in apple’s value is 5, higher.

If dp[0][3] is larger, we need to assign dp[0][3] to DP [1][3], so we get 5,

After the calculation, we can get DP [5][10], which is the maximum value that can be loaded when the backpack capacity is 10 after all things are considered.

With a general understanding of the knapsack problem, let’s look at some practical examples from LeetCode.

The instance

1049. The weight of the last stone II

If two stones are equal, return 0; if one is larger, return the difference. So there are two cases where all the stones cancel each other out or one is left, and the core of the problem returns the minimum possible weight of the last stone.

And the way we think about it, the problem we can solve is, if you divide the rock into two piles, and you subtract the two piles, how do you get the smallest difference.

If the sum of the stones is sum, one of the two piles will weigh NRG, and the other pile will be sum – NRG;

So the difference = (sum – NRG) -nrg = sum – 2nrg. We can see that the larger NRG is, the smaller the difference is. When NRG = sum/2, the difference reaches the minimum 0.

Var lastStoneWeightII = function(stones) {// let sum = stone.reduce ((s1,s2)=>{return s1+s2}); // let NRG = math.floor (sum/2); Let dp = new Array(stones.length+1).fill(0).map(()=>new Array(NRG +1).fill(0)); // Loop the array of stones, because stones[0] = 0, so we start with 1 for(let I = 1; i<=stones.length; i++){ let stone = stones[i-1]; // for(let j = 0; j<=nrg; Dp [I][j] = dp[i-1][j]; / / the current volume, if you can add stones in the if (j > = stone) {/ / if enough volume and dp [I] [j] will be equal to the load of stone and a maximum of residual capacity can be loaded together, at the same time and the maximum load on a stone. dp[i][j] =Math.max(stone+dp[i-1][j-stone],dp[i][j]); }}} // sum-2nrg; return sum - 2*dp[stones.length][nrg] }Copy the code

494. The target and

The difference is that one is the maximum size that can be filled, and the number of possibilities that can be filled.

I can still split the value of the array in half, so let’s say the negative half is NRG, sum is sum, and the positive half is sum minus NRG

Target = (sum – NRG) -nrg = sum – 2nrg, NRG = (sum – k) / 2. At this point we just want to figure out how many possibilities there are for a backpack full of NRG.

If target>sum, the total number of nums is not greater than target, then there is no way to get target. If sum minus k over 2 is a decimal, that doesn’t work either, and this is an array of integers, NRG must be an integer.

Because there is only one way to fill a backpack when the backpack capacity is 0 and that is not to fill it, so it is defined as dp[0][0] = 1;

Var findTargetSumWays = function(nums, target) {sum sum = nums.reduce((s1,s2)=>{return s1+s2}); // let diff = sum-target; / / if target > sum | | or diff % 2! == 0 if(diff<0 || diff%2 ! ==0){ return 0 } let nrg = diff/2; Let dp = new Array(nums.length+1).fill(0).map(()=>new Array(NRG +1).fill(0)); Dp [0][0] = 1; for(let i = 1; i<=nums.length; i++){ let num = nums[i-1]; for(let j = 0; j<=nrg; j++){ dp[i][j] = dp[i-1][j]; If (m > = num) {/ / not to choose the possibility of num + num the possibility of dp [I] [j] + = dp [j - num] [I - 1]. } } } return dp[nums.length][nrg] }Copy the code

To optimize the

In the above problem, we can see that we only used I (current loop), i-1(previous loop).

dp[i][j] = dp[i-1][j] + dp[i-1][j-num]

If, at this point, we reverse the cycle of NRG, j = NRG; j>=num; j–

If we change this step, we can clearly see that the condition j>=num is satisfied

Because it’s going backwards, we can think of it this way

Let’s say we’re at this point, we’re looping through I and j, and we set a one-dimensional Array, dp = new Array(NRG +1).fill(0).

The equation dp[j] = dp[j]+dp[j-num [i-1]]

Now we’re going to loop in I, and we’re going to loop in the backpack capacity to see if we can carry I.

Because we are in the reverse loop, all dp[j]+dp[j-num [i-1]] does not calculate the possibility of installing I, i.e. i-1, and j-num [i-1] is before d[j]. So that’s what I minus one came in.

Optimization results in the following method

Var findTargetSumWays = function(nums, target) {sum sum = nums.reduce((s1,s2)=>{return s1+s2}); // let diff = sum-target; / / if target > sum | | or diff % 2! == 0 if(diff<0 || diff%2 ! ==0){ return 0 } let nrg = diff/2; // define dp let dp = new Array(NRG +1).fill(0); // define the initial state dp[0] = 1; for(let i = 1; i<=nums.length; i++){ let num = nums[i-1]; for(let j = nrg; j>=num; j--){ dp[j] = dp[j]+dp[j - num] } } return dp[nrg] }Copy the code