描述

給出n個物品的體積A[i]和其價值V[i]岸夯，將他們裝入一個大小為m的背包簿姨，最多能裝入的總價值有多大堕扶？

注意事項(xiàng)

A[i], V[i], n, m均為整數(shù)爱沟。你不能將物品進(jìn)行切分徊件。你所挑選的物品總體積需要小于等于給定的m奸攻。

樣例

對于物品體積[2, 3, 5, 7]和對應(yīng)的價值[1, 5, 2, 4], 假設(shè)背包大小為10的話，最大能夠裝入的價值為9虱痕。

挑戰(zhàn)

O(n * m) memory is acceptable, can you do it in O(m) memory?

思路
在這個問題中睹耐，一件物品要么不選，要么選部翘，正好對應(yīng)于 0-1 兩個狀態(tài)硝训，所以我們一般把形如這樣的背包問題稱作 0-1 背包問題

代碼

1. 暴力解法，枚舉出所有可能性，本題是 0-1 背包問題窖梁，所以對于 n 個背包有 2^n 種可能性赘风，計算每種可能性下背包中物品的價值，最后要檢查每種可能性是否滿足題目要求纵刘，在所有滿足要求的可能性中選擇價值最大的

public class Solution {
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @param V: Given n items with value V[i]
     * @return: The maximum value
     */
    public int backPackII(int m, int[] A, int[] V) {
        int n = A.length;
        int limit = 1 << n;
        int ans = 0;
        for (int i = 0; i < limit; i++) {
            // tA 表示背包中所有物品的體積, tV 表示背包中所有物品的價值
            int tA = 0;
            int tV = 0;
            // j 的目的是用來從低位到高位來檢查當(dāng)前位代表的物品是否被選取
            for (int j = 0; j < n; j++) {
                if ((i >> j) % 2 == 1) {
                    tA += A[j];
                    tV += V[j];
                } 
            }
            if (tA <= m && tV > ans) {
                ans = tV;
            }
        }
        
        return ans;
    }
}

2. 貪心法邀窃。顯然價值越大體積越小的物品單位價值最高，我們將物品按 P[i] = val[i] / cap[i]P[i]=val[i]/cap[i] 從大到小排序假哎，再依次將物品裝入背包瞬捕，直到無法將物品裝入背包為止。但這種方法得出的結(jié)果是錯的

3. 用滾動數(shù)組和一維數(shù)組優(yōu)化過的動態(tài)規(guī)劃解法

public class Solution {
    public int backPackII(int m, int[] A, int[] V) {
        int n = A.length;
        int[] f = new int[m + 1];
        for (int i = 0; i < n; ++i) {
            for (int j = m; j >= A[i]; --j) {
                f[j] = Math.max(f[j], f[j - A[i]] + V[i]);
            }
        }
        return f[m];
    }
}