给定一个容量为c的背包，以及一组物品，每个物品的重量及价值分别存放在一个数组中:weights[0...n],values[0...n]

求得将物品放入背包后的最大价值是多少？

 

Code：自底向上

/**     *      * @param weights 每个物品的重量     * @param values 每个物品的价值     * @param c 背包容量     * @return     */    public int bestValue(int[] weights, int[] values, int c){        int m = weights.length;                int[][] dp = new int[m][c+1];        for (int i = 0; i <= c; i++) {            dp[0][i] = (i >= weights[0] ? values[0]:0);        }        for (int i = 1; i < m; i++) {            for (int j = 0; j <= c; j++) {                dp[i][j] = dp[i-1][j];                if(j >= weights[i]){                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j-weights[i]]+values[i]);                }            }        }        return dp[m-1][c];    }

 

Code：自顶向下

/**     *      * @param dp 存储记忆化空间     * @param weights 每个物品的重量     * @param values 每个物品的价值     * @param index 放入物品的编号     * @param c 背包容量     * @return     */    private int bagValue(int[][] dp, int[] weights, int[] values, int index, int c){        if (index < 0 || c <= 0) {            return 0;        }                if(dp[index][c] != Integer.MIN_VALUE){            return dp[index][c];        }                int res = bagValue(dp, weights, values, index-1, c);        if (c >= weights[index]) {            res = Math.max(res, bagValue(dp, weights, values, index-1, c-weights[index]) + values[index]);        }        dp[index][c] = res;        return res;    }        public int bestValue1(int[] weights, int[] values, int c){        int n = weights.length;        int[][] dp = new int[n][c+1];        for (int i = 0; i < n; i++) {            for (int j = 0; j < c+1; j++) {                dp[i][j] = Integer.MIN_VALUE;            }        }        return bagValue(dp, weights, values, n-1, c);    }