Bounded 01 Knapsack Guide

Introduction

The Knapsack problem is a constrained optimization problem with one or two linear, inequality constraints:
- The items are limited (i <= len(nums) -1)
- Capacity is limited (c <= Capacity)
A naive solution to this problem could be found be generating all possible subsets and isolating the subsets that match the criteria. (similar to 78. subsets and 90. subsets II). However, this solution is suboptimal by nature because it is a purely exhaustive algorithm (brute-force) with no overlapping subproblems. In other words, the solution tree in this approach will not have any repeating nodes if the input is unique. Hence no overlapping subproblems. We lose the opportunity to memoize.
The knapsack solution on the other hand will have overlapping subproblems which makes memoization possible. Asymptotically, A memoized algorithm is more optimal.
Below is a visual comparison between the solution trees of the exhaustive and the 01 knapsack approaches to a sample problem asking for subsets whose sum is equal to some targetSum:
- Suboptimal, exhaustive solution:
- Optimal memoized 01 knapsack

Classical 01 Knapsack

Given weights and profits of N items and a knapsack with a limited capacity. Find the maximum profit

Time:
- Bruteforce: O(2^N) + O(2^N) + 1 => O(2^N)
- memoized: O(N*C)

Space: O(N)

def knapsack(weights, profits, capacity):

	# helper
	def recurse(i,c):
		if c < 0 or i > len(weights)-1:  # -- NOTE [1]
			return 0

		if weights[i] > c: # if indv weight is greater than remaning capcity in sack 
			return 0

		if (i,c) in memo: # -- NOTE [1]
			return memo[(i,c)]

		res = max(profits[i] + recurse(i+1, c-weights[i]), recurse(i+1, c)) # max out of inlcude & exclude - optimization KS 

		memo[(i,c)] = res
		return res

	# main
	memo = {}
	return recurse(0, capacity)

Boolean 01 Knapsack

Variations:
- Partition list into 2 subset with equal sum
- Find a subset whose sum = k

Given N items find out if they can be partitioned into 2 subsets whose sum = trgtSum
This problem can be converted into:
Given N items, find out if there exists a subset whose sum = trgtSum/2

Unlike classical knapsack, here we have only one inequality constraint

Time:
- Bruteforce: O(2^N) + O(2^N) + 1 => O(2^N)
- memoized: O(N*trgtSum) => Pseudo polynomial aka. time does not only depend on the size of the input but also its numeric value

Space: O(N)

def bool_knapsack(nums, trgtSum):

	# helper
  def f(i, subsetSum): # i, subsetSum are two inequality constraints

		if subsetSum == 0:
			return True

		if subsetSum < 0:
			return False

		if i > len(num)-1:
			return False

		if (i, subsetSum) in memo:
			return memo[(i, subsetSum)]

	result = f(i+1, subsetSum-num[i]) or f(i+1, subsetSum) # include or exclude - boolean knapsack
	memo[(i,subsetSum)] = result
	return result

	# main
	memo = {}
	if sum(num) % 2 != 0:
		return False
	trgtSum = sum(num)//2
	return f(0, trgtSum)

Min abs difference 01 Knapsack

In the Equal subset sum problem, the sum of all items had to be divisible by 2 . Otherwise we returned False. We were 100% fair; allocating exactly half to each subset.
If sum is not divisible by 2, should we give up in despair? No! We can get as close as possible to being fair. We divide the items into 2 subsets (s1, s2) such that they have the min abs difference between their sums. This precisely is the ask in this problem.

Partition the set into two subsets with a minimum difference between their subset sums.

Time:
- Bruteforce: O(2^N) + O(2^N) + 1 => O(2^N)
- memoized: O(N*s1) => Pseudo polynomial - where s1 is the sum of the subset with larger sum
  - for ex: Time complexity of input [999, 999, 998] >> [1, 1, 2]

Space: O(N)

def minAbsDiffSubsets_knapsack(nums):
  # helper
  def f(i, s1, s2):
  
	if i == len(nums): # -- NOTE 
	  return abs(s1-s2)

	if (i, s1) in memo:
	  return memo[(i,s1)]

	result = min( f(i+1, s1+nums[i], s2), f(i+1, s1, s2+nums[i]) )
	memo[(i, s1)] = result
	return result


  # main
  memo = {}
  return f(0,0,0) #i, s1, s2
  
  # NOTE:
  # -----
  # Update diff at leaf node only
  # It's only at the leaf node that all items in the input have been categorized into one of the 2 subsets.

Count subsets 01 Knapsack

In the Equal subset sum problem, we returned True if we found a subset with a sum equal to targetSum

In this problem, we find the count of the subsets that satisfy that same condition.

Time:
- Bruteforce: O(2^N) + O(2^N) + 1 => O(2^N)
- memoized: O(N*trgtSum) => Pseudo polynomial

Space: O(N)

def count_knapsack(nums):
  # helper
  def f(i, s1, s2):
	if i == len(nums):
	  return abs(s1-s2)

	if (i, s1) in memo:
	  return memo[(i,s1)]

	result = min( f(i+1, s1+nums[i], s2), f(i+1, s1, s2+nums[i]) )
	memo[(i, s1)] = result
	return result


  # main
  memo = {}
  return f(0,0,0) #i, s1, s2

Target sum 01 Knapsack

Given a set of +ve integers, assign either + or - to the items such that the result is equal to target. Find out the total ways that can be built, whic evaluates to target.

s1 - s2 = diff :--[1]
s1 + s2 = sums(num) :--[2]
Adding [1] & [2]:
2s1 = diff + sums(num)
s1 = [ diff + sums(nums) ] / 2

Boils down to finding a subset whose sum = s1

Time:
- Bruteforce: O(2^N) + O(2^N) + 1 => O(2^N)
- memoized: O(N*trgtSum) => Pseudo polynomial

Space: O(N)

def find_target_subsets(num, s):

  # helper:
  def f(i, trgtSum):

	if trgtSum == 0:
	  return 1

	if i == len(num):
	  return 0

	if (i, trgtSum) in memo:
	   return memo[(i, trgtSum)]

	result = f(i+1, trgtSum-num[i]) + f(i+1, trgtSum)
	memo[(i,trgtSum)] = result
	return result

  # main:
  memo = {}
  if (s + sum(num)) % 2 != 0:
	return 0
  trgtSum = (s + sum(num)) / 2
  return f(0, trgtSum)

Same problem as above except zeros are also allowed in the input set. (one line change)

def findTargetSumWays(self, nums: List[int], target: int) -> int:

	# helper
	def f(i, trgtSum):

		if i == len(nums) and trgtSum == 0: # --- NOTE [1]
			return 1

		# if trgtSum == 0: #  does not work when a 0 is trailing +ve integers
		#     return 1

		if i == len(nums):
			return 0

		if trgtSum < 0:
			return 0

		if (i, trgtSum) in memo:
			return memo[(i, trgtSum)]

		result = f(i+1, trgtSum-nums[i]) + f(i+1, trgtSum)
		memo[(i,trgtSum)] = result
		return result

	# main
	nums.sort()
	memo = {}
	if (sum(nums) + target) % 2 != 0:
		return 0
	trgtSum = (sum(nums) + target) // 2
	return f(0, trgtSum)

	# NOTE [1]
	# --------
	'''
	Had nums not conatined any zeros (only +ve integeres)
	we would've afforded to return 1 (add to the count) as soon as we see a targtSum = 0
	This also holds if items included zero that is followed by +ve integers
	However, if a zero is trailing +ve integers ex: [1,2,0] we would miss one scenario that
	also adds up to trgtSum
		-> scenario [1] : 1,2 count = 1
		-> sceanrio [2] (missed scenario) : 1,2,0 count = 2 

	To overcome this we could only return 1 if:
		a. trgtSum = 0, AND
		b. i == len(nums)

	This way we would delay capturing the first scenario at the benifit of being able to capture the 2nd scenario as well 
	'''

Comments (1)

No comments yet.