Skills for tackling LeetCode problems - 0/1 Knapsack.
0/1 Knapsack can be efficiently solved by Memoization and Bottom-Up Dynamic Programming.
1. 0/1 Knapsack
Given two integer arrays to represent weights and profits of N items, we need to find a subset of these items which will give us maximum profit such that their cumulative weight is not more than a given number C. Each item can only be selected once, which means either we put an item in the knapsack or we skip it.
1] Brute-Force Solution - Recursion.
# Time complexity O(2^N). Space complexity O(N). N is the total number of items.
def solve_knapsack(profits, weights, capacity):
return recursive(profits, weights, capacity, 0)
def recursive(profits, weights, capacity, index):
# base
if capacity <= 0 or index >= len(profits):
return 0
# recursive call after choosing the element at the index
profit1 = 0
if weights[index] <= capacity:
profit1 = profits[index] + recursive(profits, weights, capacity - weights[index], index + 1)
# recursive call after excluding the element at the index
profit2 = recursive(profits, weights, capacity, index + 1)
return max(profit1, profit2)
2] Top-down Dynamic Programming with Memoization. We can more efficiently solve overlapping subproblems.
Since we have two changing values index and capacity in the recursive function recursive(), we can use a 2d array to store the results of all the solved subproblems.
# Time complexity O(N * C) since there ar N * C subproblems. Space complexity O(N * C + C).
def solve_knapsack(profits, weights, capacity):
# 2d array to store all possible profits
dp = [[-1 for _ in range(capacity + 1)] for _ in range(len(profits))]
return recursive(dp, profits, weights, capacity, 0)
def recursive(dp, profits, weights, capacity, index):
if capacity <= 0 or index >= len(profits):
return 0
if dp[index][capacity] != -1:
return dp[index][capacity]
# recursive call after choosing the element at the index
profit1 = 0
if weights[index] <= capacity:
profit1 = profits[index] + recursive(dp, profits, weights, capacity - weights[index], index + 1)
# recursive call after excluding the element at the index
profit2 = recursive(dp, profits, weights, capacity, index + 1)
dp[index][capacity] = max(profit1, profit2)
return dp[index][capacity]
3] Bottom-up Dynamic Programming. dp[i][c] will represent the maximum knapsack profit for capacity ‘c’ calculated from the first ‘I’ item. The function for the maximum profit is
dp[i][c] = max(dp[i-1][c], profit[i] + dp[i-1][c-weight[i]]).
where dp[i-1][c] is the profits excluding the ‘i’th item, and profit[i] + dp[i-1][c-weight[i]] is the profits including the ‘i’th profit.
# Time complexity O(N * C). Space complexity O(N * C).
def solve_knapsack(profits, weights, capacity):
# base
n = len(profits)
if capacity <= 0 or n == 0 or len(weights) != n:
return 0
dp = [[0 for _ in range(capacity + 1)] for _ in range(n)]
# populate the capacity = 0 colunms, the profits for 0 capacity are 0
for i in range(n):
dp[i][0] = 0
# if it can contain the first item, then add the profit
for c in range(capacity + 1):
if weights[0] <= c:
dp[0][c] = profits[0]
for i in range(n):
for c in range(capacity + 1):
profit1, profit2 = 0,0
# including the profit at the index
if weights[i] <= c:
profit1 = profits[i] + dp[i-1][c - weights[i]]
# excluding the profit at the index
profit2 = dp[i-1][c]
dp[i][c] = max(profit1, profit2)
return dp[n-1][capacity]
4] Bottom-up Dynamic Programming with a single array to reduce the space complexity to O(C). We use the same array for the previous and the next iteration.
def solve_knapsack(profits, weights, capacity):
# base
n = len(profits)
if capacity <= 0 or n == 0 or len(weights) != n:
return 0
dp = [0 for _ in range(capacity + 1)]
# if it can contain the first item, then add the profit
for c in range(capacity + 1):
if weights[0] <= c:
dp[c] = profits[0]
for i in range(1, n):
for c in range(capacity, -1, -1): # we can never overwrite dp[c - weights[i]]
profit1, profit2 = 0,0
# including the profit at the index
if weights[i] <= c:
profit1 = profits[i] + dp[c - weights[i]]
# excluding the profit at the index
profit2 = dp[c]
dp[c] = max(profit1, profit2)
return dp[capacity]
2. Equal Subset Sum Partition
Given a set of positive numbers, find if we can partition it into two subsets such that the sum of elements in both subsets is equal.
1] Basic Recursion. Two equal subsets have a sum equal to a half of the sum of all the given numbers: S/2. So the problem is the same as to find a subset of the given numbers that has a total sum of S/2.
# Time complexity O(2^N). Space complexity O(N).
def can_partition(num):
S = sum(num)
if S % 2 != 0:
return False
return recursion(num, S / 2, 0)
def recursion(num, S, index):
# base
if S == 0:
return True
n = len(num)
if n == 0 or index >= n:
return False
# recursive call after choosing the number at the index
if num[index] <= S:
if (recursion(num, S - num[index], index + 1)):
return True
# recursive call after excluding the number at the index
return recursion(num, S, index + 1)
2] Top-Down Dynamic Programming with Memoization.
# Time complexity O(N * S). Space complexity O(N * S). N is the count of total numbers and S is the totoal sum of all the numbers.
def can_partition(num):
S = sum(num)
if S % 2 != 0:
return False
dp = [[-1 for _ in range(int(S/2) + 1) ] for _ in range(len(num))]
return recursion(dp, num, int(S / 2), 0)
def recursion(dp, num, S, index):
# base
if S == 0:
return True
n = len(num)
if n == 0 or index >= n:
return False
# recursive call after choosing the number at the index
if dp[index][S] == -1:
if num[index] <= S:
if recursion(dp, num, S - num[index], index + 1):
dp[index][S] = 1
return True
# recursive call after excluding the number at the index
dp[index][S] = recursion(dp, num, S, index + 1)
return dp[index][S]
3] Bottom-Up Dynamic Programming.
# Time complexity O(N * S). Space complexity O(N * S).
def can_partition(num):
S = sum(num)
if S % 2 != 0:
return False
S = int(S / 2)
n = len(num)
dp = [[False for _ in range(S + 1)] for _ in range(n)]
for i in range(n): # for 0 sum
dp[i][0] = True
for j in range(1, S + 1): # for the first number
dp[0][j] = (num[0] == j)
for i in range(1, n):
for j in range(1, S+1):
if dp[i-1][j]: # same as the above cell
dp[i][j] = dp[i-1][j]
elif j >= num[i]:
dp[i][j] = dp[i-1][j - num[i]]
# The bottom right is the answer
return dp[n-1][S]
3. Subset Sum
Given a set of positive numbers, determine if a subset exists whose sum is equal to a given number ‘S’.
1] Bottom-up Dynamic Programming.
For every possible sum S, we have two options:
- Exclude the number. See whether we can get the sum S from the subset excluding this number
dp[index-1][S] - Include the number if its value is not more than S. See if we can find a subset to get the remaining sum
dp[index-1][s-sum[index]].
If either of the above two scenarios returns true, we can find a subset with a sum equal to S.
# Time complexity O(N * S). Space complexity O(N * S).
def can_partition(num, sum):
n = len(num)
dp = [[False for _ in range(sum + 1)] for _ in range(n)]
# for sum = 0
for i in range(n):
dp[i][0] = True
# for the first number
for s in range(1, sum + 1):
dp[0][s] = True if num[0] == s else False
for i in range(1, n):
for s in range(1, sum + 1):
# for those we can get the sum from the above cell
if dp[i-1][s]:
dp[i][s] = dp[i-1][s]
# see whether including the num at index can sum to the target
elif s >= num[i]:
dp[i][s] = dp[i - 1][s - num[i]]
# the bottom-right is the answer
return dp[n-1][sum]
Improve the algorithm to reduce the space complexity to O(S).
def can_partition(num, sum):
n = len(num)
dp = [False for _ in range(sum + 1)]
# for sum = 0
dp[0] = True
# for the first number
for s in range(1, sum+1):
dp[s] = (num[0] == s)
for i in range(1, n):
for s in range(sum, -1, -1): # reverse order
if not dp[s] and s >= num[i]:
dp[s] = dp[s - num[i]]
return dp[sum]
4. Minimum Subset Sum
Given a set of positive numbers, partition the set into two subsets with minimum difference between their subset sums.
1] Brute-Force Solution: Recursion.
# Time complexity O(2^N). Space complexity O(N).
def can_partition(num):
return recursion(num, 0, 0, 0)
def recursion(num, index, sum1, sum2):
if index == len(num):
return abs(sum1 - sum2)
# recursion call after including the number at the index in the first set
diff1 = recursion(num, index + 1, sum1 + num[index], sum2)
# recursion call after including the number at the index in the second set
diff2 = recursion(num, index + 1, sum1, sum2 + num[index])
return min(diff1, diff2)
2] Top-Down Dynamic Programming with Memoization.
def can_partition(num):
dp = [[-1 for _ in range(sum(num) + 1)] for _ in range(len(num))]
return recursion(dp, num, 0,0,0)
def recursion(dp, num, index, sum1, sum2):
# base
if index == len(num):
return abs(sum1 - sum2)
if dp[index][sum1] == -1:
diff1 = recursion(dp, num, index + 1, sum1 + num[index], sum2)
diff2 = recursion(dp, num, index + 1, sum1, sum2 + num[index])
dp[index][sum1] = min(diff1, diff2)
return dp[index][sum1]
3] Bottom-Up Dynamic Programming. This problem is equivalent to finding a subset whose sum is as close to half of the total sum S/2 as possible. (Because in this way we can get the minimum difference.) Essentially, we need to calculate all the possible sums up to S/2. To populate the array dp[totalNumbers][S/2 + 1] in the bottom fashion, for every possible sums we have two options:
- Exclude the number. See if we can get the sum
Sfrom the subset excluding the numberdp[index-1][S] - Include the number if its value is not more than
S. See if we can find a subset to get the remaining sumdp[index-1][s - num[index]].
# Time complexity O(N * S). Space complexity O(N * S).
def can_partition(num):
s = sum(num)
n = len(num)
dp = [[False for _ in range(int(s/2) + 1)] for _ in range(n)]
# for sum = 0
for i in range(n):
dp[i][0] = True
# for the first number
for j in range(int(s/2) + 1):
dp[0][j] = (num[0] == j)
# process all subsets
for i in range(1, n):
for j in range(1, int(s/2) + 1):
if dp[i-1][j]: # same as the above cells
dp[i][j] = dp[i-1][j]
elif j >= num[i]: # find subset that can sum to the target
dp[i][j] = dp[i-1][j - num[i]]
sum1 = 0
# find the larget index in the last row that is true
for i in range(int(s/2), -1, -1): # find in reversive order
if dp[n-1][i]:
sum1 = i # sum of the first subset, this sum is closest to s/2
break
sum2 = s - sum1
return abs(sum2 - sum1)
