0/1背包问题

public class beibao01 {

    public static void main(String[] args) {
        int n = 3;   //物品数量
        int m = 10; //背包容量
        int[] w = {3,4,5}; //物品重量
        int[] p = {4,5,6}; //=物品价值
        int[][] c = getPackage(n, m, w, p);
        for(int i =0; i<m+1;i++) {
            System.out.print(i + " ");
        }
        System.out.println();
        for(int i = 1; i<n+1; i++) {
            System.out.print(i + " ");
            for(int j=1; j<m+1; j++) {
                System.out.print(c[i][j] + " ");
            }
            System.out.println();
        }

    }
    
    public static int[][] getPackage(int n, int m, int[] w, int[] p){
        int[][] c = new int[n+1][m+1];
        
        for(int i = 0; i < m+1; i++) {
            c[0][i] = 0;
        }
        for(int j = 0; j<n+1; j++) {
            c[j][0] = 0;
        }
        
        for(int i = 1; i <= n; i++) {
            for (int j =1; j <= m; j++) {
                if(w[i - 1] <= j) {
                    if(c[i-1][j] < c[i-1][j - w[i-1]]+p[i-1]) {
                        c[i][j] = c[i-1][j - w[i-1]]+p[i-1];
                    }else {
                        c[i][j] = c[i-1][j];
                    }
                }else {
                    c[i][j] = c[i-1][j];
                }
            }
        }       
        return c;
    }
}

输出结果

0 1 2 3 4 5 6 7 8 9 10 
1 0 0 4 4 4 4 4 4 4 4 
2 0 0 4 5 5 5 9 9 9 9 
3 0 0 4 5 6 6 9 10 11 11