Brute force recursion to dynamic programming(knapsack problem) 03

Question

Given two arrays of length N, w[] and v[], w[i] and v[i] represent the weight and values of item i, respectively. Given a positive number bag, representing a bag with a load bag. Your items cannot exceed this weight. Return what is the most value you can hold?

Solution #1 Brute force recursion

1. Found the base case, two cases, the array of w is end or bag capacity is less than zero. Because the weight of w[i] may be zero.

2. Decision, whether the w[i] position needs to be. If necessary, the bag capacity minus the weight of w[i] and add the value of v[i]. If not necessary, skip w[i] position. Choose the maximum of the two decisions.
   

public static int myMaxValue(int[] w, int[] v, int bag) {

        return myProcess(w, v, 0, bag);
    }

    public static int myProcess(int[] w, int[] v, int index, int bag) {
        if (bag < 0) {
            return -1;
        }
        if (index == w.length) {
            return 0;
        }

        int p1 = myProcess(w, v, index + 1, bag);
        int p2 = 0;
        int next = myProcess(w, v, index + 1, bag - w[index]);
        if (next != -1) {
            p2 = next + v[index];
        }
        return Math.max(p1, p2);
    }

Solution #2 Dynamic programming

public static int myDp(int[] w, int[] v, int bag) {
        int N = w.length;
        int[][] dp = new int[N + 1][bag + 1];

        for (int index = N - 1; index >= 0; index--) {
            for (int rest = 0; rest <= bag; rest++) {
                int p1 = dp[index + 1][rest];
                int p2 = 0;
                int next = rest - w[index] < 0 ? -1 : dp[index + 1][rest - w[index]];
                if (next != -1) {
                    p2 = v[index] + dp[index + 1][rest - w[index]];
                }
                dp[index][rest] = Math.max(p1, p2);
            }
        }

        return dp[0][bag];
    }