동적설계법 배낭문제 - 2

package algorithm;

import java.util.Arrays;

public class Knapsack {

    static final int MAX_N = 100;
    static int[][] dp = new int[MAX_N][MAX_N];
    static int W;
    static int[] v;
    static int[] w;
    static int n;

    public static void main(String[] args) {

        n = 4;
        w = new int[] {2, 1, 3, 2};
        v = new int[] {3, 2, 4, 2};
        W = 5;
        // Arrays.fill(dp, -1);  error!
        for (int[] row : dp)
            Arrays.fill(row, -1);

        // int res = solve(0,W);
        // System.out.println(res);
        solve2();
    }

    private static int solve(int idx, int weight) {
        if (dp[idx][weight] >= 0) {
            return dp[idx][weight];
        }
        int res;
        if (idx == n) {
            res = 0;
        } else if ( weight < w[idx]) {  // skip
            res = solve(idx+1, weight);
        } else {  // 넣는 경우, 넣지 않는 경우.
            int a = solve(idx + 1, weight);
            int b = solve(idx + 1, weight - w[idx]) + v[idx];  // 이 경우에만 물건을 넣는 경우 v[idx]로 이때만 추가된다.
            res = Math.max(a, b);
        }

        return dp[idx][weight] = res;
    }

    private static void solve2() {  // i=idx, j=weight
        for (int[] row : dp)
            Arrays.fill(row, 0);  // -1이 아님을 주의. 캐시를 하는 것이 아니라. 전부 더할 것이다.

        for (int i = n - 1; i >= 0; i--) {
            for (int j = 0; j <= W; j++) {
                if (j < w[i]) {
                    dp[i][j] = dp[i + 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i + 1][j - w[i]] + v[i]);
                }
            }
        }

        for (int i = 0; i <= W; i++) {
            for (int j = 0; j <= W; j++) {
                System.out.print(dp[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println(dp[0][W]);
    }
}