동적설계법 - 배낭문제 -1

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);

    }

    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;
    }
}