Dynamic programming - 01 knapsack problem

The problem background ：

The thief has a capacity of W The backpack , Yes n Items , The first i Item value vi, weight wi.

The goal is ： find xi Such that for all xi = {0,1}, bring sum(xi * wi) <= W And sum(xi * vi) Maximum .

Problem solving ：

Solution 1 （ Violence goes back ）：

public class Package01 {
	
	public static int search(int W, int[] v, int[] w, int index) {
		if(index < 0)
			return 0;
		int a = W >= w[index]? search(W - w[index], v, w, index - 1) + v[index] : 0;
		int b = search(W, v, w, index - 1);
		return Math.max(a, b);
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] v = {50,200,180,225,200};
		int[] w = {5,25,30,45,50};
		int ans = search(100, v, w, 4);
		System.out.println(ans);
	}
}

Solution 2 ：

Analyze redundancy ： In both cases f(n - 1) --- f(n - 1, w) & f(n - 1, w')  ---> Cache with a two-dimensional array

public class Package01 {
	static int[][] f = new int[5][101];
	public static int search(int W, int[] v, int[] w, int index) {
		if(index < 0)
			return 0;
		if(f[index][W] > 0)
			return f[index][W];
		int a = W >= w[index]? search(W - w[index], v, w, index - 1) + v[index] : 0;
		int b = search(W, v, w, index - 1);
		f[index][W] = Math.max(a, b);
		return f[index][W];
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] v = {50,200,180,225,200};
		int[] w = {5,25,30,45,50};
		int ans = search(100, v, w, 4);
		System.out.println(ans);
	}
}

limitations ：

a. If W It's a double Type of , This caching method cannot be used

b. If W When it's worth a lot , You can't use this method

Solution 3 （ Recurrence ）：

public class Package01 {
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] v = {50,200,180,225,200};
		int[] w = {5,25,30,45,50};
		int W = 100;
		int[][] f = new int[v.length][W + 1];
		for(int i = 0; i < v.length; ++i) {
			for(int j = 0; j <= W; ++j) {
				if(i == 0) {
					f[i][j] = j >= w[i]? v[i] : 0;
				}
				else {
					int a = j >= w[i]? f[i - 1][j - w[i]] + v[i] : 0;
					int b = f[i - 1][j];
					f[i][j] = Math.max(a, b);
				}
			}
		}
		System.out.println(f[v.length - 1][W]);
	}
}

summary ：

Dynamic programming is a search algorithm without repetition and omission .

Spatial complexity ：n*W

Time complexity ：O(n*W)

expand ：

If W Particularly large , The space complexity will be very high

Improve the code ：

Ideas ：f[i] It only needs f[i - 1], Unwanted f[i - 2]; new f[i], delete f[i - 2]

Handle ： It can be used %2 The operation of （ Scrolling array ）

public class Package01 {
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] v = {50,200,180,225,200};
		int[] w = {5,25,30,45,50};
		int W = 100;
		int[][] f = new int[2][W + 1];
		for(int i = 0; i < v.length; ++i) {
			for(int j = 0; j <= W; ++j) {
				//f[i] It only needs f[i - 1], Unwanted f[i - 2]
				//new f[i], delete f[i - 2]
				f[i % 2][j] = 0;
				if(i == 0) {
					f[i % 2][j] = j >= w[i]? v[i] : 0;
				}
				else {
					int a = j >= w[i]? f[(i - 1) % 2][j - w[i]] + v[i] : 0;
					int b = f[(i - 1) % 2][j];
					f[i % 2][j] = Math.max(a, b);
				}
			}
		}
		System.out.println(f[(v.length - 1) % 2][W]);
	}
}