背包问题

问题描述

给出n个物品的体积A[i]和其价值V[i]，将他们装入一个大小为m的背包，最多能装入的总价值有多大？

核心公式：

f[i][j]=max{f[i-1][j],f[i-1][j-A[i]]+A[i]}
不放第i个物品：f[i-1][j]
放第i个物品：那么问题就转化为“前i-1件物品放入剩下的容量为j-A[i]的背包中”，此时能获得的最大体积就是f[i-1][j-A[i]]再加上通过放入第i件物品获得的体积A[i]

代码

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

问题链接