# ─── Python ──────────────────────────────────────────────────────────
 
# ══════════════════════════════════════════════════════
# 1. 0/1 Knapsack — 2D DP (also tracks which items taken)
# ══════════════════════════════════════════════════════
def knapsack_2d(weights: list[int], values: list[int], W: int):
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
 
    for i in range(1, n + 1):
        w, v = weights[i-1], values[i-1]
        for c in range(W + 1):
            dp[i][c] = dp[i-1][c]            # Skip item i
            if c >= w:
                dp[i][c] = max(dp[i][c], dp[i-1][c-w] + v)   # Take item i
 
    # Backtrack to find which items were taken
    items_taken = []
    c = W
    for i in range(n, 0, -1):
        if dp[i][c] != dp[i-1][c]:           # Item i was taken
            items_taken.append(i-1)
            c -= weights[i-1]
 
    return dp[n][W], list(reversed(items_taken))
 
# ══════════════════════════════════════════════════════
# 2. 0/1 Knapsack — Space-Optimised 1D (O(W) space)
# ══════════════════════════════════════════════════════
def knapsack(weights: list[int], values: list[int], W: int) -> int:
    dp = [0] * (W + 1)
    for w, v in zip(weights, values):
        for c in range(W, w - 1, -1):        # Right-to-left!
            dp[c] = max(dp[c], dp[c - w] + v)
    return dp[W]
 
# ══════════════════════════════════════════════════════
# 3. Subset Sum — can we make sum S from subset of nums?
# ══════════════════════════════════════════════════════
def subset_sum(nums: list[int], S: int) -> bool:
    dp = [False] * (S + 1)
    dp[0] = True                             # Empty subset sums to 0
    for num in nums:
        for s in range(S, num - 1, -1):      # Right-to-left
            dp[s] = dp[s] or dp[s - num]
    return dp[S]
 
# ══════════════════════════════════════════════════════
# 4. Partition Equal Subset Sum (LeetCode 416)
# ══════════════════════════════════════════════════════
def can_partition(nums: list[int]) -> bool:
    total = sum(nums)
    if total % 2 != 0: return False          # Odd total → impossible
    return subset_sum(nums, total // 2)
 
# Tests
weights = [2, 3, 4, 5]
values  = [3, 4, 5, 6]
W = 5
 
max_val, items = knapsack_2d(weights, values, W)
print(f"Max value: {max_val}")   # 7
print(f"Items taken (0-indexed): {items}")   # [0, 1] → weights 2+3=5
 
print(knapsack(weights, values, W))           # 7
print(subset_sum([3, 1, 1, 2, 2, 1], 5))     # True
print(can_partition([1, 5, 11, 5]))           # True (11 == 1+5+5)
print(can_partition([1, 2, 3, 5]))            # False

// ─── C++ ─────────────────────────────────────────────────────────────
#include <iostream>
#include <vector>
#include <algorithm>
 
// 1D Space-Optimised Knapsack
int knapsack(const std::vector<int>& w, const std::vector<int>& v, int W) {
    std::vector<int> dp(W+1, 0);
    for (int i = 0; i < (int)w.size(); ++i)
        for (int c = W; c >= w[i]; --c)
            dp[c] = std::max(dp[c], dp[c-w[i]] + v[i]);
    return dp[W];
}
 
// Partition Equal Subset Sum
bool canPartition(const std::vector<int>& nums) {
    int total = 0;
    for (int x : nums) total += x;
    if (total % 2) return false;
    int half = total / 2;
    std::vector<bool> dp(half+1, false);
    dp[0] = true;
    for (int x : nums)
        for (int s = half; s >= x; --s)
            dp[s] = dp[s] || dp[s-x];
    return dp[half];
}
 
int main() {
    std::cout << knapsack({2,3,4,5},{3,4,5,6},5) << "\n"; // 7
    std::cout << canPartition({1,5,11,5}) << "\n";         // 1 (true)
    std::cout << canPartition({1,2,3,5}) << "\n";          // 0 (false)
}

// ─── Java ─────────────────────────────────────────────────────────────
import java.util.*;
 
class Knapsack {
    static int knapsack(int[] w, int[] v, int W) {
        int[] dp = new int[W+1];
        for (int i=0;i<w.length;i++)
            for (int c=W;c>=w[i];c--)
                dp[c] = Math.max(dp[c], dp[c-w[i]]+v[i]);
        return dp[W];
    }
 
    static boolean canPartition(int[] nums) {
        int total = Arrays.stream(nums).sum();
        if (total%2!=0) return false;
        int half = total/2;
        boolean[] dp = new boolean[half+1];
        dp[0]=true;
        for (int x:nums)
            for (int s=half;s>=x;s--)
                dp[s]=dp[s]||dp[s-x];
        return dp[half];
    }
 
    public static void main(String[] args) {
        System.out.println(knapsack(new int[]{2,3,4,5},new int[]{3,4,5,6},5)); // 7
        System.out.println(canPartition(new int[]{1,5,11,5}));  // true
    }
}

// ─── JavaScript ───────────────────────────────────────────────────────
function knapsack(weights, values, W) {
    const dp = new Array(W+1).fill(0);
    for (let i=0;i<weights.length;i++)
        for (let c=W;c>=weights[i];c--)
            dp[c] = Math.max(dp[c], dp[c-weights[i]]+values[i]);
    return dp[W];
}
 
function canPartition(nums) {
    const total = nums.reduce((a,b)=>a+b,0);
    if (total%2!==0) return false;
    const half=total/2, dp=new Array(half+1).fill(false);
    dp[0]=true;
    for (const x of nums)
        for (let s=half;s>=x;s--)
            dp[s]=dp[s]||dp[s-x];
    return dp[half];
}
 
console.log(knapsack([2,3,4,5],[3,4,5,6],5));  // 7
console.log(canPartition([1,5,11,5]));           // true

// ─── C# ──────────────────────────────────────────────────────────────
using System;
using System.Linq;
 
class Knapsack {
    static int Solve(int[] w, int[] v, int W) {
        var dp = new int[W+1];
        for (int i=0;i<w.Length;i++)
            for (int c=W;c>=w[i];c--)
                dp[c]=Math.Max(dp[c],dp[c-w[i]]+v[i]);
        return dp[W];
    }
 
    static bool CanPartition(int[] nums) {
        int total=nums.Sum();
        if (total%2!=0) return false;
        int half=total/2;
        var dp=new bool[half+1]; dp[0]=true;
        foreach(var x in nums)
            for(int s=half;s>=x;s--)
                dp[s]=dp[s]||dp[s-x];
        return dp[half];
    }
 
    static void Main() {
        Console.WriteLine(Solve(new[]{2,3,4,5},new[]{3,4,5,6},5));   // 7
        Console.WriteLine(CanPartition(new[]{1,5,11,5}));              // True
    }
}