Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
494 views
in Technique[技术] by (71.8m points)

c# - algorithm to find the correct set of numbers

i will take either python of c# solution

i have about 200 numbers:

 19.16 
 98.48 
 20.65 
 122.08 
 26.16 
 125.83 
 473.33 
 125.92 
 3,981.21 
 16.81 
 100.00 
 43.58 
 54.19 
 19.83 
 3,850.97 
 20.83 
 20.83 
 86.81 
 37.71 
 36.33 
 6,619.42 
 264.53 
...
...

i know that in this set of numbers, there is a combination of numbers that will add up to a certain number let's say it is 2341.42

how do i find out which combination of numbers will add up to that?

i am helping someone in accounting track down the correct numbers

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

Here's a recursive function in Python that will find ALL solutions of any size with only two arguments (that you need to specify).

def find_all_sum_subsets(target_sum, numbers, offset=0):
    solutions = []
    for i in xrange(offset, len(numbers)):
        value = numbers[i]
        if target_sum == value:
            solutions.append([value])
        elif target_sum > value:
            sub_solutions = find_all_sum_subsets(target_sum - value, numbers, i + 1)
            for sub_solution in sub_solutions:
                solutions.append(sub_solution + [value])
    return solutions

Here it is working:

>>> find_all_sum_subsets(10, [1,2,3,4,5,6,7,8,9,10,11,12])
[[4, 3, 2, 1], [7, 2, 1], [6, 3, 1], [5, 4, 1], [9, 1], [5, 3, 2], [8, 2], [7, 3], [6, 4], [10]]
>>>

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...