Knapsack Problems

// items[i] = [weight, value], capacity W
public int knapsack01(int[][] items, int W) {
    int n = items.length;
    int[][] dp = new int[n+1][W+1];
    // dp[i][w] = max value using first i items, capacity w

    for (int i = 1; i <= n; i++) {
        int wt = items[i-1][0], val = items[i-1][1];
        for (int w = 0; w <= W; w++) {
            dp[i][w] = dp[i-1][w]; // skip item i
            if (wt <= w)
                dp[i][w] = Math.max(dp[i][w], dp[i-1][w - wt] + val); // take item i
        }
    }
    return dp[n][W];
}

// Space-optimized (1D)
public int knapsack01Opt(int[][] items, int W) {
    int[] dp = new int[W+1];
    for (int[] item : items) {
        int wt = item[0], val = item[1];
        for (int w = W; w >= wt; w--) // REVERSE — prevents using same item twice
            dp[w] = Math.max(dp[w], dp[w - wt] + val);
    }
    return dp[W];
}

public int unboundedKnapsack(int[][] items, int W) {
    int[] dp = new int[W+1];
    for (int w = 1; w <= W; w++)
        for (int[] item : items)
            if (item[0] <= w)
                dp[w] = Math.max(dp[w], dp[w - item[0]] + item[1]);
    // Inner loop order: FORWARD (allows using same item again)
    return dp[W];
}

public boolean canPartition(int[] nums) {
    int total = Arrays.stream(nums).sum();
    if (total % 2 != 0) return false;
    int target = total / 2;

    boolean[] dp = new boolean[target + 1];
    dp[0] = true;
    for (int num : nums)
        for (int j = target; j >= num; j--) // reverse for 0/1
            dp[j] |= dp[j - num];
    return dp[target];
}

public int countSubsets(int[] nums, int target) {
    int[] dp = new int[target + 1];
    dp[0] = 1;
    for (int num : nums)
        for (int j = target; j >= num; j--)
            dp[j] += dp[j - num];
    return dp[target];
}

// Number of ways to assign + / - to reach target
// Equivalent to: find subset S1 with S1 - (total - S1) = target
// → S1 = (total + target) / 2 → count subsets with sum S1
public int findTargetSumWays(int[] nums, int target) {
    int total = Arrays.stream(nums).sum();
    if ((total + target) % 2 != 0 || Math.abs(target) > total) return 0;
    int s1 = (total + target) / 2;
    return countSubsets(nums, s1);
}