1

I have list of numbers where numbers can be repeated, so list may look like:

[18,18,18,15,15,15,11,11,11]

I also have one number that we'll call the target. My goal is to find a set of numbers from my list that ideally sum to the target, or else are as close as possible without going over.

If target is 88, then ideal result should be: [18,18,15,15,11,11], as remainder is 0 in this case.

One more example:

List: [60,50,50,30,20]
target: `105`
Expected result: [50,50] (or may be [50,30,20])

Currently I'm first finding all possible combinations from the list numbers, and then extracting combination values from target, until remainder gets lower possible value, but that is very inefficient way, as all possible combinations count sometime gets very large number.

What may be better/efficient way for this?

Dave
  • 7,460
  • 3
  • 26
  • 39
Oto Shavadze
  • 40,603
  • 55
  • 152
  • 236
  • 1
    I’m voting to close this question because this is the knapsack problem and there's not much we can do within the confines of this site. – chx Aug 29 '22 at 20:45
  • 2
    https://stackoverflow.com/questions/4632322/finding-all-possible-combinations-of-numbers-to-reach-a-given-sum/64380474#64380474 shows how to solve a variant of this with dynamic programming. The differences being that you just one one combination, not all of them, and at the end you have to start from the largest reached result rather than the desired target. – btilly Aug 29 '22 at 20:48
  • 2
    @chx Actually it is the subset sum problem. Which is known for good reason as "the easiest hard problem". Dynamic programming solves it perfectly well. – btilly Aug 29 '22 at 20:48

1 Answers1

0

My Idea was to use a breadth-first search combined with Dynamic Programming.

 def nearest_target_sum(target_value, values):

    possible_values = {0: []}
    solution_indexes = {0: []}
    max_value_possible = 0
    values_to_be_handled = [0]

    while values_to_be_handled:
        value = values_to_be_handled.pop(0)
        solution = possible_values[value]
        solution_index = solution_indexes[value]
        if value == target_value:
            return value

        if value > max_value_possible:
            max_value_possible = value

        for i in range(len(values)):
            if i in solution_index:
                continue
            val = values[i]
            next_value = value + val
            if next_value > target_value:
                continue
            if next_value not in possible_values:
                possible_values[next_value] = solution + [val]
                solution_indexes[next_value] = solution_index + [i]
                values_to_be_handled.append(next_value)

    return max_value_possible, possible_values[max_value_possible]


print(nearest_target_sum(105, [60, 50, 50, 30, 20]))
print(nearest_target_sum(200, [60, 50, 50, 30, 20]))

Output:-

(100, [50, 50])
(190, [60, 50, 50, 30])
Hithru
  • 66
  • 1
  • 6