Do not copy, do not affectation, speak their own understanding, if there is no place with your idea ah, right, right

Knapsack problem

Backpack problem mainly refers to a given capacity of a backpack, a number of items with a certain value and weight, how to choose items into the backpack to maximize the value of items. There are also 01 knapsack and full knapsack.

The main study here is 01 backpacks, but full backpacks can also be converted to full backpacks

First simulate a scene, I am a thief, I enter a shopping mall, and there are four kinds of goods for me to steal: battery of battery car no. 1 (1000RMB,1kg), battery of battery car No. 2 (2000RMB,2kg), battery of battery car No. 3 (3000RMB,3kg), Battery no.4 of battery car (4000RMB,4kg), but I only took one backpack, and there is only one battery for each type of battery no.4. Suppose my backpack can hold 1 kg, 2 kg, 3 kg, 4 kg of these four conditions, how can I steal goods, will be able to let me go out the crime income maximization this evening?

Since I don’t know how to draw a table with nuggets, I’ll go into a little more detail about the process:

As you can see, the picture above shows how we can buy batteries with different backpack capacities to maximize our profits on this trip!

Ok, so we have drawn the table diagram of the implementation of this algorithm, so let’s now write the concrete description of the implementation of the algorithm

Thought analysis and diagrams

  • The main idea of the algorithm is solved by using dynamic programming. When traversing the ith item every time, the algorithm uses W [I] and V [I] to determine whether the item needs to be put into the backpack. That is, for a given n items, v[I] and W [I] are the value and weight of the ith item respectively, and C is the capacity of the backpack. Let v[I]][j] represent the maximum value that can fit into a backpack of capacity J in the first I items. Then we have the following results:

  • v[i][0]=v[0][j]=0; // indicates that the first row and column of the table are 0

  • When w[I]>j: v[I][j]=v[i-1][j] // When the capacity to add new goods is greater than the current backpack capacity, the previous cell loading strategy is used

  • When [I] > j w, v [I] [j] = Max {v [j], [I – 1] v [I] + v [I – 1] [j w. [I]]} / / when ready to join the new goods is greater than the current capacity of the backpack capacity, is used in a cell’s load strategy

Code implementation

  • Define constants

  • Let weight=[1,4,3,5,6]// let value=[1500,3000,2000,5000,6000]let m=4; // Let map=new Array()Copy the code

  • JS creates a two-dimensional array

  • Function map (map){for(let I =0; i<value.length; i++){ map[i]=new Array() for(let j=0; j<weight.length; J ++){map[I][j]=0}} map=initColumnAndRows(map) return map}// Create a two-dimensional array endCopy the code

  • Initialize the first row and the first column of the two-dimensional array to 0, indicating that if you don’t have a backpack, you can’t carry the goods

  • Function initColumnAndRows(map){let rowLength=map.length let columnLength=map[0]. Length for(let I =0; i<rowLength; i++){ map[i][0]=0 } for(let j=0; j<columnLength; J ++){map[0][j]=0} map=MethodData(map) return map}// Initialize the first line and end of the first columnCopy the code

  • The knapsack problem actually solves the core code

  • Function MethodData(map){for(let I =1; i<map.length; i++){ for(let j=1; j<map[i].length; Map [I][j]=map[i-1][j]}else{// If (weight[i-1]>j){map[I][j]=map[i-1][j] =map[i-1][j]}else{// Otherwise the value of the current item will be compared to see if the value of the previous line is higher, // J-weight [i-1] is the value of the item in your current row // plus the amount of available space for the item // higher // j-weight[i-1] is the amount of available space for the item map[i][j]=Math.max(map[i-1][j],value[i-1]+map[i-1][j-weight[i-1]]) } } } return map; }// The dynamic programming handler endsCopy the code

  • Calling function code

  •   map=initMap(map)console.log(map)
Copy the code

The above code to solve 01 knapsack problem, let’s study the full knapsack problem

Complete knapsack problem

A backpack can hold n items, the weight and value of item J are respectivelyIf the maximum weight limit of the backpack is B, how to select items to put into the backpack to maximize the total value of the backpack?

Here is a sample problem for everyone to understand:

Recently, a shopping mall because of the anniversary, opened the “0 yuan purchase” activity. During the activity, consumers can purchase specified goods with 0 yuan by combining the coupons in their hands.

The clever little tuan wants to use an algorithm to help him calculate quickly: for a given price of goods, use vouchers to make up the price, but the total value of the vouchers can not exceed the price of the goods. Because the number of vouchers is limited, the use of fewer vouchers can achieve maximum value, that is, the best offer.

Suppose there are 100 yuan of goods, and there are four kinds of vouchers: 50 yuan, 30 yuan, 20 yuan and 5 yuan. The best offer is two 50 yuan vouchers. If you have a $65 item available, the best offer is two $30 vouchers and a $5 voucher.

Please help small groups to use a piece of code to implement the voucher calculation.

This is the sixth question in the 2020 front-end written test of Meituan Autumn recruit

The following code directly, this I recorded a video tutorial: www.bilibili.com/video/BV1LU…

Function fn(coins,price){function fn(coins,price){// Let dp=new Array(price+1). Fill (Infinity) dp[0]=0 i<=price; If (I >=coin){//coin:50 //dp[I]=Infinity dp[i-coin] dp[i]=Math.min(dp[i],dp[i-coin]+1) } } } return dp[price]===Infinity? [price]}console.log(fn([50,30,20,5],110))Copy the code

The above