Algorithm (7) : graphic dynamic programming

Introduction of algorithm

Dynamic programming, the big problem is divided into small problems to solve, step by step to obtain the optimal solution of the processing algorithm

Different from greedy algorithms

• Both divide big problems into smaller sub-problems

• Dynamic programming is essentially divide-and-conquer and the solution of redundancy. The solution of each subproblem is saved so that it can be directly referenced when it is encountered again later, avoiding double calculation. One of the salient features of dynamic programming is that there will be a large number of repeated subproblems, so the previous solution can be directly used

• Each operation of a greedy algorithm has a direct impact on the result (dealing with a smaller and smaller range of problems), whereas dynamic programming does not. The greedy algorithm selects the solution for each subproblem and cannot go back. Dynamic programming will select the current according to the previous selection results, and has the function of backtracking (for example, backpack problem, the smaller backpack in the same row with the same capacity is the best solution, overturning the previous selection). Dynamic programming is mainly applied to two-dimensional or three-dimensional problems, while greed is generally one-dimensional problems

• Greedy algorithm results in the optimal approximate solution, and dynamic programming is the optimal solution

• Dynamic programming is similar to the way of searching or filling a table. Problems with optimal substructure can be dynamically programmed, otherwise greedy algorithm is used

case

The example here is from the book “Diagrams of Algorithms”

Case a

Backpack problem: There is a backpack with a capacity of 4 pounds and the following items are available

The goal to achieve is to load the maximum total value of the backpack, and the weight does not exceed.

Similar problems were introduced in the previous article “Greedy algorithms” to find approximate solutions, now use dynamic programming to find optimal solutions.

Solving similar problems can be broken down into small problems one by one. Assume that there are knapsacks with different capacities divided into 1, 2, 3, and 4 (the rule of allocating capacity is an integer multiple of the minimum weight) :

Such as:

For the first line (I =1), only the guitar is currently available, so

For the second line (I =2), there are currently guitars and audio options available, so

For the third line (I =3), guitar, stereo and computer can be selected at present, so

All of the above fit the formula:

F(I,j) = Max {F(i-1,j), W(I) + F(I,j = J-v (I))} is Max {the value of the above cell, the value of the current commodity + the maximum value of the remaining space} F(I,j) represents the maximum value that can be obtained from row I and column J, W(I) represents the value of the row, and V(I) here represents the weight of the space occupied by the row, F(I,j = J-V (I)) : hypothesisCopy the code

For example, F(3,4) = Max {F(2,4), F(3,3) + 2000} = Max {3000, 1500 + 2000} = 3500, the time complexity of this problem O(V*N),V bit backpack capacity, N is the total number of items, that is, the total number of table grids.

The above backpack space is generally divided into integer multiples of the size of the smallest item (here is the guitar, which occupies 1 pound). If there is an extra 0.5 pound item, it needs to be divided into finer granularity (0.5,1,1.5,2,2.5,3,3.5,4).

And as you go down a column, the maximum value doesn’t go down, because every time you compute it, you take the maximum value. And the result does not depend on the order of the rows, for example:

Using the above formula, when the backpack is 4 pounds, the maximum value that can be loaded is still 3500:

Calculation process:

I = 1: (1, 1), (1, 2), (1, 3) : because when j = 1, 2, 3 < (V (I) = 4) so the overflow, empty (1, 4) : Max {F (I – 1, j), W (I) + F (I, j (I) – V)} = Max {F (0, 4), 3000 + F (1, 0)} = 3000

I = 2: (2, 1), (2, 2) : because when j = 1, 2 < (V (I) = 4, V (I – 1) = 3) so the overflow, empty: (2, 3) Max {F (1, 3), W (2) + F (2, 0)} (2, 4) = 2000: Max {F (1, 4), W (2) + F (2, 1)} = Max = 3000 {3000, 2000 + 0}

I = 3: (3, 1) : Max {F (2, 1), 1500 + F (3, 0)} (3, 2) = 1500: Max {F (2, 2), 1500 + F (3, 1)} = 1500 (because only a guitar, cannot be repeated in a) (3, 3) : Max {F(2,3), 1500 + F(3,2)} = Max {200,1500} = 2000 Max {F(2,4), 1500 + F(3,3)} = Max {3000,3500} = 3500

Case 2

Optimization of travel itinerary:

Suppose you have two days to travel to the following places, how to make good use of it, so that the overall score is high:

The problem is actually a backpack, but the capacity becomes the time, the processing method is the same as above, and soon you can get:

F(I,j) = Max {F(i-1,j), W(I) + F(I, j-v (I))} is Max {the value of the above cell, the value of the current commodity + the value of the remaining space} F(I,j) represents the maximum value that can be obtained from row I and column J, W(I) represents the value of the line, and V(I) here represents the weight of the space occupied by the lineCopy the code

limitations

One of the limitations of dynamic planning is that it considers the whole item to be processed each time, and cannot support the practice of taking away a few points. For example, the first case is modified as:

Backpack 4 pounds, 1. A full bag of 10 pounds of oats at $6 a pound; 2. A whole 10-pound bag of rice at $3 a pound; 3. A whole 10-pound bag of potatoes at $5 a pound; Because the whole bag doesn't fit, it's no longer a case of either taking or not taking, it's a case of unpacking and taking part of the item, in which case dynamic programming can't handle it. Dynamic programming is only suitable for whole item processing. But using the greedy algorithm introduced before is very appropriate, a strong take the most expensive, take out a most expensive.Copy the code

The second limitation of dynamic programming is that it cannot handle interdependent situations. For example, in case 2, it increases the number of locations it wants to go to

It takes a long time to get from these places, because you have to travel from London to Paris, which takes 0.5 days (1.5 days includes 0.5 days of travel cost). If we go to all three places, the total need is 1.5 * 3= 4.5 days? No, once you arrive in Paris, you'll only need 1.5 + 1 + 1 = 3.5 days to play all 3 places in a row. This will be"The Tower of Paris"loading"Pack"Will make the"Sorbonne","Paris Hospital."When it gets cheaper, you can't model it using dynamic programming.Copy the code

Dynamic programming, while powerful, can solve subproblems and use those answers to solve larger problems. But dynamic programming works only if each subproblem is discrete, that is, independent of other subproblems.

Java implementation

Case 1: Public class KnapsackProblem {public static void main(String[] args){public static void main(String[] args){float knapsackWeight = 4;
		float[] itemsWeights = new float[] {1, 4, 3};
		float[] itemsPrices = new float[] {1500, 3000, 2000}; 
		float[][] table = knapsackSolution(knapsackWeight, itemsWeights, itemsPrices);
		
		for (int line = 0; line < table.length; line++ ) {
			System.out.println("-----------------line =" + line);
			for (int colume = 0; colume < table[line].length; colume++ ) {
				System.out.println(table[line][colume] + ","); }}} /** ** @param knapsackWeight total capacity * @param itemsWeights Capacity occupied by each item * @param itemsPrices value * @return
	 */
	public static float[][] knapsackSolution(float knapsackWeight, float[] itemsWeights, float[] itemsPrices) {
		if(itemsWeights.length ! = itemsPrices.length) { throw new IllegalArgumentException(); } int lines = itemsprices.length; // Calculate the minimum space of the backpack partition, i.e. the weight of each column in the table is column * minWeightfloat minWeight = getMinWeight(itemsWeights); Int colums = (int) (knapsackWeight/minWeight); System.out.println("lines = " + lines + ",colums = " + colums + ",minWeight = "+ minWeight); // Create a table object with lines and colums columnsfloat[][] table = new float[lines][colums];
	
		for (int line = 0; line < lines; line++ ) {
			for (int colume = 0; colume < colums; colume++ ) {
				
				float left = table[(line - 1) < 0 ? 0 : (line - 1) ][colume];
				floatright = 0; (colume +1)*minWeight = (colume +1)*minWeightif((colume +1)*minWeight >= itemsWeights[line]) {// Obtain the remaining space of the backpackfloatfreeWeight = ((colume+1)*minWeight - itemsWeights[line]); Int freeColumn = (int) (freeWeight/minWeight) -1;if(freeColumn >= 0 && line > 0) {// Because the value of the position in the same column is higher as you go down, Right = itemsPrices[line] + table[line-1][freeColumn]; right = itemsPrices[line] + table[line-1][freeColumn]; }else{ right = itemsPrices[line]; } } table[line][colume] = Math.max(left, right); }}returntable; } /** * Gets the minimum weight of all items ** @param itemsWeights The amount of space each item occupies * @return
	 */
	public static float getMinWeight(float[] itemsWeights) {
		float min = itemsWeights[0];
		
		for (floatweight : itemsWeights) { min = min > weight ? weight : min; } / / keep up to 2 decimal places, and the default nonzero will carry a 1.222 - > 1.23 why String. / / the valueOf, refer to https://www.cnblogs.com/LeoBoy/p/6056394.htmlreturnnew BigDecimal(String.valueOf(min)).setScale(2, RoundingMode.UP).floatValue(); }}Copy the code

The following information is displayed after the main method is executed: Lines = 3, colums = 4, minWeight = 1.0 -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- line = 0, 1500.0, 1500.0, 1500.0, 1500.0, -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- line = 1, 1500.0, 1500.0, 1500.0, 3000.0, -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- line = 2, 1500.0, 1500.0, 2000.0, 3500.0,Copy the code

Float knapsackWeight = 2; Float [] itemsWeights = new float[] {0.5f,0.5f,1,2 0.5f}; float[] itemsWeights = new float[] {0.5f,0.5f,1,2 0.5f}; Float [] itemsPrices = new float[] {7,6,9,9,8}; float[] itemsPrices = new float[] {7,6,9,9,8};