CODEWITHSUNDEEP
pythondynamic-programming
Vikram Murthy
Vikram Murthy

Reputation: 323

dynamic programming - find numbers that add up to a sum

EDIT - based on some feedback, i have decided to mention the problem statement. If some of you want to check what i have tried, please feel free to scroll below the "--------------" line

we need to be able to pick line items from an invoice and one of the ways we are trying to make sure we get the total amount correct is the following ..suppose i manage to extract an array of numbers [ 235, 120, 340, 600, 150000, 1175 ] i would find out the largest subset that adds up to one of the numbers in the array , which in this case is going to be 1175 = 235 + 340 + 600 .. i have tried a partial DP approach to it ( details below ) , but if this info is good enough i would like a complete DP solution, minus the hacks i had to use ..appreciate it.

"-----------------------------------------------------------"

im new to DP and wanted to implement a solution (at scale) for our product. Basically we need to find all line items in a table that add up to the total and since we dont use "keywords" one of the solutions was to find all possible numbers and then add up subsets to see which subset resulted in the biggest number. Theoretically this always gave us the right answer but my implementation in DP looks a little hackey .. pfb the code and i will have the queries at the end ..thanks for your patience

import numpy as np

#main_arr = [ 3, 4, 1, 8, 10, 16 ]
main_arr = [ 3, 4, 1, 7, 15, 23, 25, 36 ]

sorted_arr_ = sorted( main_arr )

matrix_ = dict()

def calcMatrix():
        for outer_ in sorted_arr_:
                for inner_ in sorted_arr_:
                        if outer_ == inner_: continue
                        matrix_[ str(outer_)+'-'+str(inner_) ] = inner_ + outer_
calcMatrix()

print( matrix_ )

mem_dict_ = dict()
for ctr in range(1, max(main_arr)):
        if ctr in sorted_arr_:
                mem_dict_[ ctr ] = str(ctr)
        else:
                mem_dict_[ ctr ] = '0'

def search_matrix( balance ):
        for key, val in matrix_.items():
                if val == balance: return key

        return None
def search_mem( balance ):
        for key, val in mem_dict_.items():
                if balance == key and val != '0': return val

        return None

def findAlt( bal, avoid ):
        for idx in range( bal ):
                major, minor = idx, bal-idx
                maj, mino = None, None
                print('In findAlt->', major, minor)
                if major != avoid and minor != avoid:
                        matrix_res_major = search_matrix( major )
                        matrix_res_minor = search_matrix( minor )
                        mem_res_major = search_mem( major )
                        mem_res_minor = search_mem( minor )
                        maj = matrix_res_major if mem_res_major is None else mem_res_major
                        mino = matrix_res_minor if mem_res_minor is None else mem_res_minor
                        if maj is not None and mino is not None: return maj+mino

def recur( updated_idx, main_idx ):
        if updated_idx <= 0 : return None

        bal_ = sorted_arr_[ main_idx ] - sorted_arr_[ updated_idx-1 ]
        print( 'updated_idx, main_idx, bal_, sorted_arr_[ updated_idx ], sorted_arr_[ updated_idx-1 ] = ',\
                updated_idx, main_idx, bal_, sorted_arr_[ updated_idx ], sorted_arr_[ updated_idx-1 ] )

        pos_key_ = search_matrix( bal_ )
        pos_mem_key_bal_ = search_mem( bal_ )
        pos_mem_key_ = search_matrix( sorted_arr_[ main_idx ] )
        print( pos_key_, pos_mem_key_bal_, pos_mem_key_ )

        if pos_key_ is not None :
                if str(sorted_arr_[ updated_idx-1 ]) not in str(pos_key_):
                        mem_dict_[ sorted_arr_[ main_idx ] ] = str(pos_key_)+'-'+str(sorted_arr_[ updated_idx-1 ])
                        print('Updated mem with key (a) = ', sorted_arr_[ main_idx ], ' with str = ', \
                                str(pos_key_)+str(sorted_arr_[ updated_idx-1 ]) )
                else:
                        posKey = findAlt( bal_, sorted_arr_[ updated_idx-1 ] )
                        if posKey is not None:
                                mem_dict_[ sorted_arr_[ main_idx ] ] = str(posKey)+'-'+\
                                                                        str(sorted_arr_[ updated_idx-1 ])
                                print('Updated mem with key (a.1) = ', sorted_arr_[ main_idx ], ' with str = ', \
                                str(posKey)+str(sorted_arr_[ updated_idx-1 ]) )

        elif pos_key_ is None and pos_mem_key_bal_ is not None and str(sorted_arr_[ updated_idx-1 ]) \
                        not in str( pos_mem_key_bal_ ):
                mem_dict_[ sorted_arr_[ main_idx ] ] = str(pos_mem_key_bal_)+'-'+str(sorted_arr_[ updated_idx-1 ])
                print('Updated mem with key (b) = ', sorted_arr_[ main_idx ], ' with str = ', \
                        str(pos_mem_key_bal_)+str(sorted_arr_[ updated_idx-1 ]) )
        else:
                recur( updated_idx-1, main_idx )
for i in range( 2, len(sorted_arr_) ):
        recur( i, i )

so first i create a matrix that calculates the pair wise sum of all elements and use it as a base to find numbers that could be potential sums of the elements. Then while iterating through the sorted input array, i try and create a memoized array that holds sums of members of the array. This works in most cases but in case the subset contains more than 3 elements ( meaning its a sum of more than 3 numbers ) it can fail and hence i had to add that hackey method findAlt ..bottomline is that though this works, i m not happy with the code. I am quite sure this can be done in 10-15 lines of code but i have tried multiple iterations and now making the same mistakes. Any pointers will be greatly appreciated.

Upvotes: 0

Views: 908

Answers (1)

Axeltherabbit
Axeltherabbit

Reputation: 737

Have a look here: Algorithm to find which numbers from a list of size n sum to another number

This is my solution

(I'm assuming : the numbers in the solution are unique, all the numbers positive and the target greater than zero)

recursive approach

def find_longest_sum(array: list, target: int):
   solution = []
   array = sorted(array)
   def rec_finder(sublst: list, s: int):
      nonlocal solution
      if s == target and len(sublst) > len(solution):
         solution = sublst
      else:
         for n in array:
            if s+n > target:
               break
            if n not in sublst:
               rec_finder(sublst + [n], s+n)
   rec_finder([],0)
   return solution

not recursive approach

def find_longest_sum_not_rec(array: list, target: int):
   array = sorted(array)
   solutions = [[n] for n in array]
   solution = []

   while solutions:
      new_solutions = []
      for sol in solutions:
         for n in array:
            if n not in sol:
               # Note here I'm calling sum for simplicity but
               # you'd want to save the sum and reuse it 
               # like I did for the recursive solution,
               # probably a NamedTuple would be a fine solution
               if sum(sol)+n < target:
                  new_solutions.append(sol+[n])
               elif sum(sol)+n == target and len(solution) < len(sol)+1:
                  solution = sol+[n]
                  break
               else:
                  break
      solutions = new_solutions
   return solution

print(find_longest_sum([1,2,3,5], 8)) #[1, 2, 5]
print(find_longest_sum_not_rec([1,2,3,5], 8)) #[1, 2, 5]

Upvotes: 1

Related Questions