0/1 Knapsack & Subset Sum

# 0/1 Knapsack: Items = [1,2,3], Weights = [1,2,3], Values = [10,20,30], Capacity = 4
#
# dp[i][w] = i items tak ke saath capacity w ka maximum value
#
# Capacity — 0 1 2 3 4
# Items ?
# 0 (none) 0 0 0 0 0
# 1 (w=1, v=10) 0 10 10 10 10
# 2 (w=2, v=20) 0 10 20 30 30
# 3 (w=3, v=30) 0 10 20 30 40
#
# Har cell mein decision: item include karo ya mat karo
# Include: val[i-1] + dp[i-1][w - wt[i-1]]
# Exclude: dp[i-1][w]
# Max lo dono mein se

def knapsack(W, wt, val, n):
 # dp[i][w] = i items tak capacity w ka max value
 dp = [[0] * (W + 1) for _ in range(n + 1)]
 
 for i in range(1, n + 1):
 for w in range(1, W + 1):
 if wt[i - 1] <= w:
 # Item include kar sakte hain — max lo include/exclude mein se
 include = val[i - 1] + dp[i - 1][w - wt[i - 1]]
 exclude = dp[i - 1][w]
 dp[i][w] = max(include, exclude)
 else:
 # Weight zyada hai — sirf exclude
 dp[i][w] = dp[i - 1][w]
 
 return dp[n][W]

# Example
val = [60, 100, 120]
wt = [10, 20, 30]
W = 50
n = len(val)
print(f"Maximum value: {knapsack(W, wt, val, n)}") # 220

# Subset Sum — kya sum = target possible hai?
def subsetSum(arr, target):
 n = len(arr)
 dp = [[False] * (target + 1) for _ in range(n + 1)]
 
 # 0 elements se sirf 0 sum possible hai
 for i in range(n + 1):
 dp[i][0] = True
 
 for i in range(1, n + 1):
 for s in range(1, target + 1):
 if arr[i - 1] <= s:
 # Include ya exclude
 dp[i][s] = dp[i - 1][s] or dp[i - 1][s - arr[i - 1]]
 else:
 dp[i][s] = dp[i - 1][s]
 
 return dp[n][target]

# Example
arr = [3, 34, 4, 12, 5, 2]
target = 9
print(f"Sum {target} possible: {subsetSum(arr, target)}") # True (4+5)

# Equal Partition — array ko 2 equal sum subsets mein todo
def equalPartition(arr):
 total = sum(arr)
 if total % 2 != 0:
 return False # Odd sum — impossible!
 return subsetSum(arr, total // 2)

# Example
arr = [1, 5, 11, 5]
print(f"Equal partition possible: {equalPartition(arr)}") # True
# [1,5,5] aur [11] — dono ka sum = 11

# Count Subsets — kitne subsets ka sum = target
def countSubsets(arr, target):
 n = len(arr)
 dp = [[0] * (target + 1) for _ in range(n + 1)]
 
 for i in range(n + 1):
 dp[i][0] = 1 # 0 sum ka 1 subset hai — empty subset
 
 for i in range(1, n + 1):
 for s in range(1, target + 1):
 if arr[i - 1] <= s:
 dp[i][s] = dp[i - 1][s] + dp[i - 1][s - arr[i - 1]]
 else:
 dp[i][s] = dp[i - 1][s]
 
 return dp[n][target]

# Example
arr = [1, 2, 3, 3]
target = 6
print(f"Subsets with sum {target}: {countSubsets(arr, target)}") # 3

# Unbounded Knapsack — same item baar baar le sakte ho
def unboundedKnapsack(W, wt, val, n):
 dp = [0] * (W + 1)
 
 for w in range(1, W + 1):
 for i in range(n):
 if wt[i] <= w:
 dp[w] = max(dp[w], val[i] + dp[w - wt[i]])
 
 return dp[W]

# Coin Change bhi unbounded hai — same coin baar baar le sakte ho
def coinChange(coins, amount):
 dp = [float('inf')] * (amount + 1)
 dp[0] = 0
 for i in range(1, amount + 1):
 for coin in coins:
 if coin <= i and dp[i - coin] != float('inf'):
 dp[i] = min(dp[i], dp[i - coin] + 1)
 return dp[amount] if dp[amount] != float('inf') else -1