1public class Solution {
2
3    public int solve(int[] values, int[] weights, int capacity) {
4        int n = values.length;
5        // Start recursion from last item
6        return knapsackRec(n - 1, values, weights, capacity);
7    }
8
9    // index -> current item we are allowed to consider (0..index)
10    // capacity -> remaining capacity of knapsack
11    public int knapsackRec(int index, int[] values, int[] weights, int capacity) {
12
13        // Base case:
14        // No items left OR no capacity left
15        if (index < 0 || capacity == 0) {
16            return 0;
17        }
18
19        // Case 1: Skip current item
20        int skip = knapsackRec(index - 1, values, weights, capacity);
21
22        // Case 2: Pick current item (only if it fits)
23        int pick = 0;
24        if (weights[index] <= capacity) {
25            pick = values[index]
26                 + knapsackRec(index - 1, values, weights,
27                               capacity - weights[index]);
28        }
29
30        // Return the better of pick or skip
31        return Math.max(pick, skip);
32    }
33}

1import java.util.Arrays;
2
3public class Solution {
4
5    public int solve(int[] values, int[] weights, int capacity) {
6        int n = values.length;
7
8        // dp[index][capacity] stores max value for this state
9        int[][] dp = new int[n][capacity + 1];
10
11        // Initialize dp with -1 (means not computed)
12        for (int i = 0; i < n; i++) {
13            Arrays.fill(dp[i], -1);
14        }
15
16        return knapsackMemo(n - 1, values, weights, capacity, dp);
17    }
18
19    public int knapsackMemo(int index, int[] values, int[] weights,
20                             int capacity, int[][] dp) {
21
22        // Base case
23        if (index < 0 || capacity == 0) {
24            return 0;
25        }
26
27        // If already computed, return stored answer
28        if (dp[index][capacity] != -1) {
29            return dp[index][capacity];
30        }
31
32        // Skip current item
33        int skip = knapsackMemo(index - 1, values, weights, capacity, dp);
34
35        // Pick current item (if it fits)
36        int pick = 0;
37        if (weights[index] <= capacity) {
38            pick = values[index]
39                 + knapsackMemo(index - 1, values, weights,
40                                capacity - weights[index], dp);
41        }
42
43        // Store and return result
44        dp[index][capacity] = Math.max(pick, skip);
45        return dp[index][capacity];
46    }
47}

1public class Solution {
2
3    public int solve(int[] values, int[] weights, int capacity) {
4        int n = values.length;
5
6        // dp[i][c] = max value using first i items with capacity c
7        int[][] dp = new int[n + 1][capacity + 1];
8
9        // Base cases:
10        // dp[0][*] = 0  -> no items
11        // dp[*][0] = 0  -> no capacity
12        // (Java initializes to 0 by default)
13
14        for (int i = 1; i <= n; i++) {
15            for (int c = 1; c <= capacity; c++) {
16
17                // Skip current item
18                dp[i][c] = dp[i - 1][c];
19
20                // Pick current item if it fits
21                if (weights[i - 1] <= c) {
22                    dp[i][c] = Math.max(
23                        dp[i][c],
24                        dp[i - 1][c - weights[i - 1]] + values[i - 1]
25                    );
26                }
27            }
28        }
29
30        // Final answer using all items and full capacity
31        return dp[n][capacity];
32    }
33}

1public class Solution {
2
3    public int solve(int[] values, int[] weights, int capacity) {
4        int n = values.length;
5
6        // dp[c] = max value achievable with capacity c
7        int[] dp = new int[capacity + 1];
8
9        // Loop through each item
10        for (int i = 0; i < n; i++) {
11
12            // IMPORTANT:
13            // Loop capacity BACKWARDS to avoid reusing same item
14            for (int c = capacity; c >= weights[i]; c--) {
15
16                dp[c] = Math.max(
17                    dp[c],                       // skip item
18                    dp[c - weights[i]] + values[i] // pick item
19                );
20            }
21        }
22
23        return dp[capacity];
24    }
25}