深度优先

这个家伙好懒，除了文章什么都没留下

0%

【算法】背包问题-四种解法（穷举，递归，二维数组，一维数组）

发表于 分类于
本文字数： 2.8k 阅读时长 ≈ 3 分钟

01背包问题，是用来介绍动态规划算法最经典的例子，网上关于01背包问题的讲解也很多。

我写这篇的不在于把这个问题讲得透彻，主要写下四种大概思路。

01背包的状态转换方程 f[i,j] = Max{ f[i-1,j-Wi]+Pi( j >= Wi ), f[i-1,j] }

f[i,j]表示在前i件物品中选择若干件放在承重为 j 的背包中，可以取得的最大价值。
Pi表示第i件物品的价值。
决策：为了背包中物品总价值最大化，第 i件物品应该放入背包中吗 ？
题目描述：

有编号分别为a,b,c,d,e的五件物品，它们的重量分别是2,2,6,5,4，它们的价值分别是6,3,5,4,6，现在给你个承重为10的背包，如何让背包里装入的物品具有最大的价值总和？

一、穷举（主要就是要不要，和放不放得下的问题）

由于物件应该有用户输入，所以数量是不确定的。用二进制穷举能很好的解决这个问题。这里省略输入过程。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public class A {

	public static void main(String[] args) {

		int n=5;
		int[] weight={2,2,6,5,4};
		int[] value={6,3,5,4,6};
		int bigBao=10;
		
		int max=(int)Math.pow(2, n);
		int[] er=new int[n];
		
		int M=0;
		for (int i = 1; i < max; i++) {
			er=getData(i,er);
			
			//算空间，和价值
			int sum=0;
			int jiazhi=0;
			for (int j = 0; j < er.length; j++) {
				sum+=weight[j]*er[j];
				if(sum>bigBao){
					break;
				}
				jiazhi+=value[j]*er[j];
			}
			if(jiazhi>M){
				M=jiazhi;
			}
		}
		System.out.println(M);
	}
	
	//转成二进制
	private static int[] getData(int i,int[] er) {
		int k=er.length-1;
		while(i!=0){
			er[k]=i%2;
			i=i/2;
			k--;
		}
		return er;
	}
}

二、递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class B{

	static int bigBao;
	static int n=5;
	static int[] weight={0,3,4,5};//{2,2,6,5,4}
	static int[] value={0,4,5,6};//{6,3,5,4,6}
	
	public static void main(String[] args) {
		
		System.out.println(getM(3,10));

	}

	private static int getM(int i, int v) {
		if(i<0||v<0)
			return 0;
		int k=getBool(i,v);//看装不装的下
		
		return Math.max(getM(i-1,v-weight[i])+k, getM(i-1,v));//要或者不要
	}

	//装不装得下
	private static int getBool(int i, int v) {
		if(weight[i]>v)
			return 0;
		else
			return value[i];
	}
}

三、二维数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class  C {

	public static void main(String[] args) {
		
		int n=5;
		int[] weight={0,4,5,6,2,2};
		int[] value={0,6,4,5,3,6};
		int bigBao=10;
		
		int[][] arr=new int[n+1][bigBao+1];
		

		for (int i = 1; i < weight.length; i++) {
			for (int j = 1; j < arr[0].length; j++) {
				if(j>=weight[i])
					arr[i][j]=Math.max(arr[i-1][j],arr[i-1][j-weight[i]]+value[i]);
				else
					arr[i][j]=arr[i-1][j];
			}
		}
		
		//打表输出
		for (int i = 0; i < weight.length; i++) {
			for (int j = 0; j < arr[0].length; j++) {
				System.out.print(arr[i][j]+" ");
			}
			System.out.println();
		}
	}
}

四、由二维转一维数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class D {


	public static void main(String[] args) {
		
		int n=5;
		int[] weight={0,3,2,5};
		int[] value={0,4,3,6};
		int bigBao=10;
		
		int[] arr=new int[bigBao+1];
		
		for (int i = 1; i < weight.length; i++) {
			for (int j = arr.length-1; j >0; j--) {
				if(j>=weight[i]){
					arr[j]=Math.max(arr[j],arr[j-weight[i]]+value[i]);
				}
			}
			for (int j = 0; j < arr.length; j++) {
				System.out.print(arr[j]+" ");
			}
			System.out.println();				
		}
	}
}

PS：能力有限，有些地方我也表述不清楚。反正我是懂了的