常用十大算法（三）— 動态規劃算法

部落格說明

文章所涉及的資料來自網際網路整理和個人總結，意在于個人學習和經驗彙總，如有什麼地方侵權，請聯系本人删除，謝謝！

介紹

動态規劃(Dynamic Programming)算法的核心思想是：将大問題劃分為小問題進行解決，進而一步步擷取最優解的處理算法

動态規劃算法與分治算法類似，其基本思想也是将待求解問題分解成若幹個子問題，先求解子問題，然後從這些子問題的解得到原問題的解。

與分治法不同的是，适合于用動态規劃求解的問題，經分解得到子問題往往不是互相獨立的。 ( 即下一個子階段的求解是建立在上一個子階段的解的基礎上，進行進一步的求解 )

動态規劃可以通過填表的方式來逐漸推進，得到最優解

背包問題

思路

背包問題主要是指一個給定容量的背包、若幹具有一定價值和重量的物品，如何選擇物品放入背包使物品的價值最大。其中又分01背包和完全背包(完全背包指的是：每種物品都有無限件可用)

這裡的問題屬于01背包，即每個物品最多放一個。而無限背包可以轉化為01背包。

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

(1)  v[i][0]=v[0][j]=0; //表示 填入表 第一行和第一列是0

(2) 當w[i]> j 時：v[i][j]=v[i-1][j]   // 當準備加入新增的商品的容量大于 目前背包的容量時，就直接使用上一個單元格的裝入政策

(3) 當j>=w[i]時： v[i][j]=max{v[i-1][j], v[i]+v[i-1][j-w[i]]}  
// 當 準備加入的新增的商品的容量小于等于目前背包的容量,

代碼實作

package com.guizimo;

public class KnapsackProblem {

	public static void main(String[] args) {
		int[] w = {1, 4, 3};//物品的重量
		int[] val = {1500, 3000, 2000}; //物品的價格
		int m = 4; //總重量
		int n = val.length; //價格的種類
		
		//建立二維數組
		//v[i][j] 表示在的i個物品中能夠裝入容量為j的背包中的最大價值
		int[][] v = new int[n+1][m+1];
		//輔助二維數組
		int[][] path = new int[n+1][m+1];
		
		//初始化第一行和第一列
		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];
					}
				}
			}
		}
		
		//價格表
		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("第%d個商品放入背包\n", i); 
				j -= w[i-1];
			}
			i--;
		}
	}

}

感謝

尚矽谷

以及勤勞的自己，個人部落格，GitHub