Knapsack variation to find a specified sum with

find_sum_with_limit.py

# Dynamic programm O(K X N X S)
class Knapsack:

  def find(self, values, K, S):
    N = len(values) 
    
    R = [ [ [None for s in range(S + 1)] for k in range(K+1) ] for n in range(N + 1) ]

    # initialize for the base cases
    # for k = 0 and k =1
    for n in range(N + 1):
      for s in range(S + 1):
        R[n][0][s] = 0
      
    # for n = 0 (no element)
    for k in range(K + 1):
      for s in range(S + 1):
        R[0][k][s] = 0
      
    # for s = 0, target sum is 0
    for n in range(N + 1):
      for k in range(K + 1):
        R[n][k][0] = 0

    for n in range(1, N + 1):
      for k in range(1, K + 1):
        for s in range(1, S + 1):
          v = values[n-1]  
          if v <=s and s == R[n-1][k-1][s -v] + v :
            R[n][k][s] = R[n-1][k-1][s - v] + v
          else:
            R[n][k][s] = R[n-1][k][s]
    answer = []
    #back trace

    n = N
    k = K
    s = S
    while (n > 0 and k > 0 and s > 0):
      v = values[n-1]
      if s >= v and R[n][k][s] == R[n-1][k-1][s - v] + v:
        answer.append(v)
        n -= 1
        k -= 1
        s -= v
      else:
        n -=1

    return answer


# brute force DFS O(N X N!)
class DfsSearch:
  def __init__(self):
    self.map = {}
    self.found = []

  def find(self, input, capacity, target):
    numbers = []
    self.found = []
    current = 0
    for i in range(len(input)):
      numbers.append(input[i])
      capacity -=1
      current += input[i]
      self.search(input, capacity, i, numbers, current, target)
      numbers.pop()
      capacity +=1
      current -= input[i]
    return self.found
  
  def search(self, input, capacity, i, numbers, current, target):
    if len(self.found) > 0:
      return

    elif current == target:
      self.found = list(numbers)
      return
    elif capacity == 0 or current > target:
      return

    for pos in range(i+1, len(input), 1):
      numbers.append(input[pos])
      capacity -= 1
      current += input[pos]
      self.search(input, capacity, pos, numbers, current, target)
      numbers.pop()
      capacity +=1
      current -= input[pos]
    
  
  

d = DfsSearch()
input = [1,2 ,4, 3, 5, 9]
k = 3
s = 18
print ("DFS : input = {} k = {} s= {} output ={}".format(input, k, s, d.find(input, k, s )))

dp = Knapsack()

print ("DP : input = {} k = {} s= {} output ={}".format(input, k, s, dp.find(input, k, s )))

k = 4
s = 9
print ("DFS : input = {} k = {} s= {} output ={}".format(input, k, s, d.find(input, k, s )))
print ("DP : input = {} k = {} s= {} output ={}".format(input, k, s, dp.find(input, k, s )))

k = 4
s = 6
print ("DFS : input = {} k = {} s= {} output ={}".format(input, k, s, d.find(input, k, s )))
print ("DP : input = {} k = {} s= {} output ={}".format(input, k, s, dp.find(input, k, s )))

k = 4
s = 100
print ("DFS : input = {} k = {} s= {} output ={}".format(input, k, s, d.find(input, k, s )))
print ("DP : input = {} k = {} s= {} output ={}".format(input, k, s, dp.find(input, k, s )))