Commonly used ten algorithms (three) - dynamic programming algorithm

Commonly used ten algorithms (three) – dynamic programming algorithm

The blog instructions

The information involved in the article comes from the Internet collation and personal summary, meaning is the summary of personal learning and experience, if there is any infringement, please contact me to delete, thank you!

introduce

The core idea of Dynamic Programming algorithm is to divide big problems into small problems for solving, so as to obtain the optimal solution step by step

Dynamic programming algorithm is similar to divide-and-conquer algorithm. Its basic idea is to decompose the problem to be solved into several sub-problems, solve the sub-problems first, and then obtain the solution of the original problem from the solution of these sub-problems.

Different from the divide-and-conquer method, the subproblems which are suitable for solving by dynamic programming are not independent. (That is, the solution of the next sub-stage is based on the solution of the previous sub-stage and further solution is carried out)

Dynamic programming can be advanced step by step by filling in the form to get the optimal solution

Knapsack problem

Train of thought

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 problem here belongs to the 01 backpack, which means that each item can hold at most one item. Infinite knapsack can be converted to 01 knapsack.

The main idea of the algorithm, using dynamic programming to solve. For the ith item traversed each time, according to W [I] and V [I], it is determined whether the item needs to be put into the backpack. That is, for a given n items, let v[I] and W [I] be the value and weight of the ith item respectively, and C be the capacity of the backpack. Let v[I][j] represent the maximum value of the first I items that can fit into a backpack of capacity J.

(1) v[i][0]=v[0][j]=0; When w[I]> j: v[I][j]=v[i-1][j] // When the capacity of the newly added goods is greater than the current backpack capacity, we directly use the loading strategy of the previous cell. V [I] [j] = Max {v [j], [I - 1] v [I] + v [I - 1] [j w. [I]]} / / when the goods ready to join the new capacity is less than or equal to the current capacity of backpack,Copy the code

Code implementation

package com.guizimo;

public class KnapsackProblem {

	public static void main(String[] args) {
		int[] w = {1.4.3};// The weight of the item
		int[] val = {1500.3000.2000}; // The price of the item
		int m = 4; The total weight / /
		int n = val.length; // Type of price
		
		// Create a two-dimensional array
		//v[I][j] represents the maximum value of I items that can fit into a backpack of capacity J
		int[][] v = new int[n+1][m+1];
		// Auxiliary two-dimensional array
		int[][] path = new int[n+1][m+1];
		
		// Initialize the first row and column
		for(int i = 0; i < v.length; i++) {
			v[i][0] = 0;
		}
		for(int i=0; i < v[0].length; i++) {
			v[0][i] = 0;
		}
		
		for(int i = 1; i < v.length; i++) { 
			for(int j = 1; j < v[0].length; j++) {
				if(w[i-1] > j) {
					v[i][j] = v[i-1][j];
				} else {
					if(v[i - 1][j] < val[i - 1] + v[i - 1][j - w[i - 1]]) {
						v[i][j] = val[i - 1] + v[i - 1][j - w[i - 1]];
						path[i][j] = 1;
					} else {
						v[i][j] = v[i - 1][j]; }}}}/ / price list
		for(int i =0; i < v.length; i++) {for(int j = 0; j < v[i].length; j++) { System.out.print(v[i][j] +"");
			}
			System.out.println();
		}
		
		System.out.println("= = = = = = = = = = = = = = = = = = = = = = = = = = = =");

		int i = path.length - 1;
		int j = path[0].length - 1;
		while(i > 0 && j > 0 ) {
			if(path[i][j] == 1) {
				System.out.printf("Item %d into backpack \n", i); 
				j -= w[i-1]; } i--; }}}Copy the code

Thank you

Yet in silicon valley

And hard-working self, personal blog, GitHub

Commonly used ten algorithms (three) – dynamic programming algorithm