搞了一個早上，才確切明白了這個道理
問題：有編號分別為a,b,c,d,e的五件物品，它們的重量分別是2,2,6,5,4，它們的價值分別是6,3,5,4,6，現在給你個承重為10的背包，如何讓背包里裝入的物品具有最大的價值總和？
重新定義問題：
1.有承重分別為1-10的背包10個 2.編號分別為a,b,c,d,e的物品各一個 
3. 從e物品開始依次放入1-10個背包，分別得到最大的價值總和 4. 把d物品放入依次放入存在e物品的1-10個背包，如果價值更高，替換掉e（） 5. c,b,a同理。。。 
思路： 1. 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件物品應該放入背包中嗎 ？ 2. 以a8（行為a，列為的8的單元格）舉例 f[i,j] = a8 = 15 f[i-1,j] = b8 = 9 f[i-1,j-Wi] 表示我有一個承重為6的背包（等于當前背包承重減去物品a的重量），當只有物品b,c,d,e四件可選時，這個背包能裝入的最大價值 f[i-1,j-Wi] +Pi =b(8 - 2) + 6 = b6 + 6 = 15
public class test3 { public static void main(String[] args) { int m = 10;//最大限重 int n = 3;//總量的個數 int w[] = { 3, 4, 5 };//每個的數量 int p[] = { 4, 5, 6 }; int c[][] = BackPack_Solution(m, n, w, p); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { System.out.PRint(c[i][j] + "/t"); if (j == m) { System.out.println(); } } } } public static int[][] BackPack_Solution(int m, int n, int[] w, int[] p) { // c[i][v]表示前i件物品恰放入一個重量為m的背包可以獲得的最大價值 int c[][] = new int[n + 1][m + 1]; for (int i = 0; i < n + 1; i++) c[i][0] = 0; for (int j = 0; j < m + 1; j++) c[0][j] = 0; for (int i = 1; i < n + 1; i++) { for (int j = 1; j < m + 1; j++) { // 當物品為i件重量為j時，如果第i件的重量(w[i-1])小于重量j時，c[i][j]為下列兩種情況之一： // (1)物品i不放入背包中，所以c[i][j]為c[i-1][j]的值 // (2)物品i放入背包中，則背包剩余重量為j-w[i-1],所以c[i][j]為c[i-1][j-w[i-1]]的值加上當前物品i的價值 if (w[i - 1] <= j) { if (c[i - 1][j] < (c[i - 1][j - w[i - 1]] + p[i - 1])) c[i][j] = c[i - 1][j - w[i - 1]] + p[i - 1]; else c[i][j] = c[i - 1][j]; } else c[i][j] = c[i - 1][j]; } } return c; }}新聞熱點
疑難解答
