Dynamic programming algorithm

Introduction to dynamic programming algorithms

  • 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 solutions 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.
  • The essence of dynamic programming is recursion, the core is to find the way of state transition, write dp equation.

Best practices for dynamic programming algorithms – Knapsack problems

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
  • Items to be loaded must not be duplicated

Analysis and illustration of ideas:

  • 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. Each time I go through the number oneiOne item, according tow[i]andv[i]To determine if the item needs to be placed in the backpack. That is, for a givennOne item, setv[i] 、w[i]For the firstiAn object ofThe value ofandThe weight of the.CFor the backpackcapacity. To makev[i][j]Said in the previousiOne item can fit into a capacity ofjThe greatest value in a backpack. Then we have the following results:
(1) v[i][0]=v[0][j]=0; // fill in the first row and column with 0
(2When w[I]> J: v[I][j]=v[I -1][j] V [I][j]=v[i-1][j] =v[i-1][j]
(3J >=w[I] : v[I][j]= Max {v[I -1][j], v[i]+v[i-1][j-w[i]]}
// When the capacity of the new item I to be added w[I] is less than or equal to the current backpack capacity j:
// How to load:
v[i-1[j] : is the maximum load of the last cell v[I]: represents the value of the current commodity v[I -1][j-w[I]] : load I -1Therefore, when j>=w[I] : v[I][j]= Max {v[I -1][j], v[i]+v[i-1][j-w[I]]Copy the code
  • Graphical analysis: pack filling process

Dynamic programming – knapsack problem code implementation

public class KnapsackProblem {
	public static void main(String[] args) {
		int[] w = { 1.4.3 };// Record the weight of the item
		int[] val = { 1500.3000.2000 }; Val [I] = val[I] = val[I]
		int m = 4; // Record the capacity of the backpack
		int n = val.length; // The number of items

		// Create a two-dimensional array,
		// v[I][j] represents the maximum value of the first I items that can fit into a backpack of capacity J
		int[][] v = new int[n + 1][m + 1];
		// To keep track of the items put in, we make a two-dimensional array
		int[][] path = new int[n + 1][m + 1];

		// Initialize the first row and column, which are not handled in this program, because the default is 0
		for (int i = 0; i < v.length; i++) {
			v[i][0] = 0; // Set the first column to 0
		}
		for (int i = 0; i < v[0].length; i++) {
			v[0][i] = 0; // Set the first line to 0
		}

		// Dynamically plan the processing according to the previous formula
		for (int i = 1; i < v.length; i++) { // Don't deal with the first line where I starts at 1
			for (int j = 1; j < v[0].length; j++) {// do not deal with the first column, j starts at 1
				/ / formula
				V [I][j]=v[i-1][j] =v[i-1][j]
				if (w[i - 1] > j) { W [I] = w[I -1] = w[I -1
					v[i][j] = v[i - 1][j];
				} else {
					/ / description:
					// Since our I starts at 1, the formula needs to be adjusted to
					// v[i][j]=Math.max(v[i-1][j], val[i-1]+v[i-1][j-w[i-1]]);
					// v[i][j] = Math.max(v[i - 1][j], val[i - 1] + v[i - 1][j - w[i - 1]]);
					// In order to record the goods stored in the backpack, we can not directly use the above formula, we need to use if-else to express the formula
					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]].// Record the current situation to path, just for printing and viewing the effect is convenient, does not affect the algorithm idea
						path[i][j] = 1;
					} else {
						v[i][j] = v[i - 1][j]; }}}}// Print v to see what's going on
		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();
		}

		// Output path
		System.out.println("-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --");
		for (int i = 0; i < path.length; i++) {
			for (int j = 0; j < path[0].length; j++) {
				System.out.print(path[i][j] + "");
			}
			System.out.println();
		}

		System.out.println("= = = = = = = = = = = = = = = = = = = = = = = = = = = =");
		// Outputs what items we put in at the end
		// Iterate through the path, so that the output will get all the places put in, in fact we only need the last place
// for(int i = 0; i < path.length; i++) {
// for(int j=0; j < path[i].length; j++) {
// if(path[i][j] == 1) {
// system.out. printf(" put %d item into backpack \n", I);
/ /}
/ /}
/ /}

		/ / think
		int i = path.length - 1; // Maximum index of rows
		int j = path[0].length - 1; // The maximum index of the column
		while (i > 0 && j > 0) { // Start at the end of the path
			if (path[i][j] == 1) {
				System.out.printf("The %d item is placed in the backpack \n", i);
				j -= w[i - 1]; // w[i-1]} i--; }}}Copy the code

LeetCode dynamic programming example