0-1 背包 §

有一批物品，物品存在重量和价值两项属性。在一个总重量的限制下，求可以获取到的最大总价值，每项物品最多只可以被选取一次。

public int zeroOnePackage(int capacity, int[] fees
        , int[] values) {
    int len = fees.length;
    int[] dpArr = new int[len][capacity];
    for (int j = 0; j < capacity; j++) {
        dp[0][j] = j < fees[0] ? 0 : values[0];
    }
 
    for (int i = 1; i < len; i++) {
        for (int j = 0; j < capacity; j++) {
            int sum1 = dpArr[i - 1][j];
            int sum2 = j >= fees[i] 
                ? dpArr[i - 1][j - fees[i]] + values[j] : 0;
            dpArr[i][j] = Math.max(sum1, sum2);
        }
    }
    
    return dpArr[len - 1][capacity];
}