public class 背包問題 {

    public static void main(String[] args) {

        int[] w = {1, 2, 3};  // 物品重量
        int[] val = {6, 10, 12};  // 物品價值
        int m = 5;  // 背包容量
        int n = val.length;  //

        // 創(chuàng)建二維數(shù)組
        int[][] v = new int[n + 1][m + 1];

        // 將第一行和第一列賦值為0
        for (int i = 0; i < v.length; i++) {
            v[i][0] = 0;
        }

        for (int i = 0; i < v[0].length; i++) {
            v[0][i] = 0;
        }

        // 動態(tài)處理
        for (int i = 1; i < v.length; i++) {
            for (int j = 1; j < v[0].length; j++) {


                if (w[i - 1] > j) {
                    // 不裝入背包
                    v[i][j] = v[i - 1][j];
                } else {
                    // 裝入背包
                    v[i][j] = Math.max(v[i - 1][j], val[i - 1] + v[i - 1][j - w[i - 1]]);
                }
            }
        }

        // 輸出二維數(shù)組
        for (int i = 1; i < v.length; i++) {
            for (int j = 1; j < v[0].length; j++) {
                System.out.print(v[i][j] + "\t");
            }
            System.out.println();
        }
    }
}