0/1 Knapsack

Each item can only be selected once.

Bottom-up Approach

Let dp[i][c] represents the maximum profit for capacity c for the first i items.

Recurrence:

dp[i][c] = max(dp[i-1][c], dp[i-1][c-w[i]]+p[i]) iff (c - w[i]) >= 0

First attempt uses O(N*C) space:

def solve_knapsack(profits, weights, capacity):
  # omit sanity check
  
  n = len(profits)
  dp = [[0 for x in range(capacity+1)] for y in range(n)]
  
  # fill initial states
  for i in range(0, n): # with 0 capacity
    dp[i][0] = 0
  for c in range(0, capacity+1): # with only first item
    if weights[0] <= c:
      dp[0][c] = profits[0]
      
  # fill dp table
  for i in range(1, n):
    for c in range(1, capacity+1):
      idx = c - weights[i]
      dp[i][c] = max(dp[i-1][c], 
                     0 if idx < 0 else dp[i-1][idx] + profits[i])
  
  # return ans
  return dp[n-1][capacity]

Second attempt uses O(C)space:

Dimension reduction: use the same array for the previous & next iteration.

In order to update dp[c], we would access dp[c] and dp[c-weights[i]].

dp[c] is fine, whereas dp[c-weights[i]] might be overridden since weights[i] > 0 as we need the value from previous iteration. Solution is to traverse from capacity -> 0instead.

def solve_knapsack(profits, weights, capacity):
  # omit sanity check
  
  n = len(profits)
  dp = [0 for x in range(capacity+1)]
  
  # fill initial states, only with first item
  for c in range(0, capacity+1):
    if weights[0] <= c:
      dp[c] = profits[0]
  
  # fill dp array
  for i in range(1, n):
    for c in range(capacity, -1, -1):
      idx = c - weights[i]
      dp[c] = max(dp[c], 0 if idx < 0 else dp[idx] + profits[i])

  # return ans
  return dp[capacity]

Equal Subset Sum Partition

Problem Statement

Given a set of positive numbers, find if we can partition it into two subsets such that the sum of elements in both the subsets is equal.

Recurrence

dp[i][s] represents whether it's possible (True/False) to have sum of s for the first i items.

dp[i][s] = dp[i-1][s] or dp[i-1][s-a[i]] iff s-a[i] > 0

First Attempt

def can_partition(num):
  total_sum = 0
  for n in num:
    total_sum += n
  if total_sum % 2 == 1:
    return False
  half_sum = int(total_sum / 2)

  dp = [[0 for x in range(half_sum+1)] for y in range(len(num))]

  for s in range(half_sum+1):
    dp[0][s] = False
  for i in range(len(num)):
    dp[i][0] = True

  for i in range(1, len(num)):
    for s in range(1, half_sum+1):
      idx = s - num[i]
      dp[i][s] = dp[i-1][s] or (False if idx < 0 else dp[i-1][idx])
  
  return dp[len(num)-1][half_sum]

Second Attempt

// TODO

Subset Sum

Problem Statement

Given a set of positive numbers, determine if there exists a subset whose sum is equal to a given number S.

Recurrence

dp[i][s] = dp[i-1][s] or dp[i-1][s-num[i]] iff s-num[i] > 0

dp[s] = dp[s] or dp[s-num[i]] while traversing from sum -> 0.

Solution

def can_partition(num, sum):
  # omit edge case handling
  dp = [False for x in range(sum+1)]
  
  # prepare first row
  dp[0] = True
  for s in range(1, sum+1):
    dp[s] = (num[0] == s)
  
  for i in range(1, len(num)):
    for s in range(sum, -1, -1):
      dp[s] = dp[s] or (False if s-num[i] < 0 else dp[s-num[i]])
  
  return dp[sum]

Minimum Subset Sum Difference

Problem Statement

Given a set of positive numbers, partition the set into two subsets with a minimum difference between their subset sums.

Recurrence

// TODO

Solution