Java常用算法三：01背包問題

文章目錄

• 一、動态規劃
• 1、簡介
• 2、應用場景：背包問題
• 二、01背包問題
• 1.1 分析過程
• 1.2 java實作01背包問題求解

筆記來源：尚矽谷

1. 動态規劃（Dynamic Programming）算法的核心思想是：将大問題劃分為小問題進行解決，進而一步步擷取最優解的處理算法
2. 動态規劃算法與分治算法類似，其基本思想也是将待求解問題分解成若幹個子問題，先求解子問題，然後從這些子問題的解得到原問題的解。
3. 與分治法不同的是，适合于用動态規劃求解的問題，經分解得到子問題往往不是互相獨立的。（即下一個子階段的求解是建立在上一個子階段的解的基礎上，進行進一步的求解）
4. 動态規劃可以通過填表的方式來逐漸推進，得到最優解.

以下是經典的01背包問題【每個物品不能重複】：

1. 要求達到的目标為裝入的背包的總價值最大，并且重量不超出
2. 要求裝入的物品不能重複

問題如上

1. 我們首先構造一張最大價值表【比如（吉他i，1磅j）表示在前i個物品中能夠裝入容量為j的背包中的最大價值】，0磅，1磅。。。代表目前背包容量：

1. 從吉他開始往裡面填入，當背包為0磅時，吉他不能放入，是以背包此時最大價值（吉他，0磅）=0，同理，當背包容量為1磅時，吉他可以放入，是以最大價值為吉他的價值：1500

   

2. 因為吉他隻能放一個，是以接下來的最大價值全部填寫1500

1. 接下來我們分析音響

   音響在背包為0磅時不能放入，是以（音響，0磅）=0，當背包為1磅時，音響重量為4磅，也不能放入，是以直接複制在背包為1磅時裝吉他的最大價值：

   

2. 當背包為2磅和3磅時，同理。

   

3. 當背包為4磅時，音響可以裝入，且沒有空餘空間。這時就要分析，我們裝入音響，背包最大價值有沒有上面一個方格【在背包為4磅時裝吉他的最大價值】高，如果有，則直接替換，沒有，則依然複制：

   

4. 分析電腦，我們運用之前的政策，可以解決3磅之前的問題：

   

5. 最關鍵的是：然後對于4磅，我們嘗試裝入電腦，且有空餘空間，則将max【剩餘空間最大價值】加上：

   

   然後将這個價值3500與上面一個方格的3000對比，發現3500大，是以填3500（GL）

算法的主要思想，利用動态規劃來解決。每次周遊到的第i個物品，根據w[i]和v[i]來确定是否需要将該物品放入背包中。即對于給定的n個物品，設v[i]、w[i]分别為第i個物品的價值和重量, C為背包的容量。再令v[i] [j]表示在前i個物品中能夠裝入容量為j的背包中的最大價值。則我們有下面的結果:

代碼如下：

public class DP {

	public static void main(String[] args) {
		int[] weight = {1, 4, 3};//物品的重量
		int[] value = {1500,3000,2000};//物品的價值
		int capacity = 4;//背包的容量
		int n = value.length;//物品的個數
		
		//為了記錄放入商品的情況，我們定義一個二維數組
		int[][]path = new int[n+1][capacity+1];
		
		
		//建立二維數組，表
		//v[i][j]表示在前i個物品中能夠裝入容量為j的背包中的最大價值
		int[][] v = new int[n+1][capacity+1];
		
		//初始化第一行和第一列【預設是0，可不處理】
		
		
		//動态規劃處理
		for(int i = 1; i < v.length; i++) {//不處理第一行
			for(int j = 1; j < v[0].length; j++) {//不處理第一列
				if(weight[i-1] > j) {//因為我們程式i是從1開始的，是以原來公式中的w[i]修改成w[i-1]
					//不可以裝入
					v[i][j] = v[i-1][j];
				}else {
					//可以裝入
					//v[i][j] = Math.max(v[i-1][j], value[i-1] + v[i-1][j-weight[i-1]]);
					//為了記錄商品存放到背包的情況，不能直接使用上面公式
					if(v[i-1][j] < value[i-1] + v[i-1][j-weight[i-1]]) {
						v[i][j] = value[i-1] + v[i-1][j-weight[i-1]];
						//把目前情況記錄到path
						path[i][j] = 1;
					}else {
						v[i][j] = v[i-1][j];
					}
				}
			}
		}
		
		//列印數組
		printTable(v);
		
		System.out.println("===================================");
	
		int i = path.length - 1; //行的最大下标
		int j = path[0].length - 1;
		//列的最大下标
		while(i > 0 && j > 0){//從path的最後開始找
			if(path[i][j] == 1) {
				System.out.printf("第%d個商品放入背包\n", i);
				j-=weight[i-1];
			}
			i--;
		}
	}
	
	private static void printTable(int[][] v) {
		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();
		}
	}

}


           

列印結果如下：