操屁眼的视频在线免费看,日本在线综合一区二区,久久在线观看免费视频,欧美日韩精品久久综

01背包問題

有N件物品和一個容量為V的背包。第i件物品的體積是c[i]，價值是w[i]。求解將哪些物品裝入背包可使價值總和最大。

從這個題目中可以看出，01背包的特點就是：每種物品僅有一件完全背包問題算法，可以選擇放或不放。

其狀態轉移方程是：

f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}

填表

要理解上面的那個公式，需要學會填表。

假設

n=5, C=13, w={4,5,4,3,10}, v={9,10,9,2,24}

公式說明

假如背包要放第i件物品，

此時如果不放第i件物品，那么問題就轉化為“前i-1件物品放入重量是w的背包中”，價值為f[i-1,j]；

如果放第i件物品，那么問題就轉化為“前i-1件物品放入剩下的重量為j-Wi的背包中”完全背包問題算法，此時能獲得的最大價值就是f[i-1,j-Wi]再加上通過放入第i件物品獲得的價值Pi，此時只要比較f[i-1,j]和f[i-1,j-Wi]+Pi那個大就能獲取到背包里最大的價值是多少了。

代碼

public class Test {    public static int getMaxValue(int[] weight, int[] value, int w, int n) {      // 創建一個二維數組，橫列是物品的價值，豎列是物品的重量        int[][] table = new int[n + 1][w + 1];        for (int i = 1; i <= n; i++) { //物品            for (int j = 1; j <= w; j++) {  //背包大小                if (weight[i] > j) {                    //當前物品i的重量比背包容量j大，裝不下，肯定就是不裝                    table[i][j] = table[i - 1][j];                } else {                  //裝得下，Max{裝物品i， 不裝物品i}                    table[i][j] = Math.max(table[i - 1][j], table[i - 1][j - weight[i]] + value[i]);                }            }        }        return table[n][w];    }
    public static void main(String[] args) {        int n = 5, w = 13;                //物品個數，背包容量        int[] value = {0,9,10,9,2,24};    //各個物品的價值        int[] weight = {0,4,5,4,3,10};    //各個物品的重量        System.out.println(getMaxValue(weight, value, w, n));    }}

參考資料

往期精選

聲明：發布此文是出于傳遞更多知識以供交流學習之目的。若有來源標注錯誤或侵犯了您的合法權益，請作者持權屬證明與我們聯系，我們將及時更正、刪除，謝謝。