Backpack II

Given n items with size Ai and value Vi, and a backpack with size m. What's the maximum value can you put into the backpack?

01完全背包 背包问题第一讲

即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是： f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}

    public int backPackII(int m, int[] A, int V[]) {
        // write your code here
        int[] dp = new int[m + 1];
        for(int i = 0; i < A.length; i++){
            for(int j = m; j >= 0; j--){
                if( j - A[i] >= 0  ){
                    dp[j] = Math.max(dp[j], dp[j - A[i]] + V[i]);
                }
            }
        }
        return dp[m];
    }