preface

I saw an interesting question about an interview process when I was watching an official account. The general question process is as follows:

A: Have you ever written about waterfalls?

B: I wrote about constant width waterfall flow. The implementation is when the user pulls to the bottom a certain height, the back end requests a certain number of images, and then inserts them into the page.

A: Let me ask, how to minimize the height difference between several rows of pictures?

B: The data that needs to be sent from the back end contains the height of the picture. Then I can see which column has the smallest height, insert the new picture into that column, and then see which column has the smallest height.

A: I don’t think you understand my question. I mean, how to sort the images sent from the back end so that the height difference between the columns is minimized?

B :(thinks for a while) sorry, I have no idea on this question.

This topic I feel very interesting, so for this problem, launched a more memorable exploration journey

Problem analysis

A simple transformation of the problem can be described as taking any number and dividing it into specific groups so that the sums of each group are as equal as possible

So how to solve this problem?

My previous approach to solving this kind of problem was to first find the law, find the internal common ground, and then calculate, so I first tried to explore this problem according to this method

Instead of looking at one group, let’s look at two groups

In the case of two groups, it’s easy to imagine just taking one group and trying to get half of the sum

Then this problem is transformed into the 01 knapsack problem

0-1 backpack problem

Condition: The number in the array is the weight value of the knapsack problem, and the number in the array is the value of the knapsack problem.

Question: Which items are in the backpack that add up to the nearest half of the total value?

01 Backpack handling depends on taking or not taking

The idea of solving 0-1 knapsack problem by dynamic programming is simply stated.

F (1, 2, 3, 4… I)(j) represents the maximum value that can be taken out of I items when the backpack is J

Use w(I),v(I) to represent the weight per value of the ith item

Take the expression f(1,2,3…. i-1)(j-w(i))+v(i)

The expression f(1,2,3…. i-1)(j)

Get the state transition equation f (I) (j) = Max (f (I – 1) (I) (j – w) + v (I), f (I – 1) (j)) 1, 2, 3… I is dropped into I

chooseOrNot=(List, halfNum) = >{
        let len = List.length
        let f = new Array(len)
        f[- 1] = new Array(halfNum+1).fill(0) // make f[0-1][j] exist
        let selected = []
        for(let i = 0 ; i < len ; i++){ 
            f[i] = [] // Create a two-dimensional array
            for(let j=0; j<=halfNum; j++){ 
                if( j < List[i] ){ 
                    f[i][j] = f[i- 1][j] // The object is larger than the backpack
                }else{
                    f[i][j] = Math.max(f[i- 1][j], f[i- 1][j-List[i]]+List[i])
                }
            }
        }
        let j = halfNum, w = 0
        for(let i=len- 1; i>=0; i--){
            if(f[i][j] > f[i- 1][j]){
                selected.push(i)
                j = j - List[i]
                w +=  List[i]
            }
        }
        return [f[len- 1][halfNum], selected]
    }
Copy the code

“The three-body problem”

Using the method described above, which is actually a backtracking method, can we get the optimal solution to divide the array into three groups? I substituted the previous example [2,3,4,5,6] and I got [2,4],[5],[3,6] every time I could, which is obviously not optimal.

Then there is the long inquiry into the problem of dividing any number into three groups so that the sums of each group are as equal as possible…

I was obsessed for about two days with what I call the three-body problem, disordered and chaotic.

NP complete problem

Asked my combinatorial mathematics teacher, the teacher let me look at THE NP complete problem, after looking up some information, I found that this problem may be a NPC problem, do not see do not know a startled, this problem can directly top to the ceiling of mathematics. At the beginning of the Millennium problem, we may not be able to find an optimal solution for such problems, but time complexity can often be greatly reduced by computing approximate solutions.

Greedy algorithm

Going back to the ‘three-body problem’, greedy algorithms are a good solution when the data is fairly uniform

One way to mimic the problem of the way children choose teams for games is the greedy algorithm, which iterates over the numbers in descending order, assigning each of them to any subset with a smaller sum. The running time of this method is O (n log n). This heuristic works well in practice when the numbers in the set are the same size or smaller than their cardinality, but does not guarantee the best possible partitioning.

That’s what we call waterfall flow, and of course we have to sort it, and it’s a little bit easier to extend it to n

threeBody = (array,n) = > {
	array.sort((a, b) = > {
		return b - a
	})
	let list=[]
	for (let j = 0; j < n; j++) {
		list[j] = []
	}
	let arr=[]
	for (let i = 0; i < array.length; i++) {
		for (let j = 0; j < n; j++) {
			arr[j]=sum(list[j])
		}
		min = Math.min(... arr)for (let j = 0; j < n; j++) {
			if(min==arr[j]){
				list[j].push(array[i])
				break}}}return(list,arr)
}
Copy the code

Of course, there are different solutions to these problems depending on the size and scope of the data. For example, for the data containing large numbers, if the monomer is greater than the average, it can be divided into a separate category first, and then the remaining data can be processed. For example, the divide-and-conquer solution mentioned in this paper is an efficient solution when there is less data.

Write in the back

This is a very interesting algorithm problem, and we can try different algorithms to try to get the most efficient and accurate approximation solution. I wonder if big guys have a better way?