optimization - Combination Algorithm to Find Target Value from Finite List of Values -
i have problem in have finite set of values, say:
[1, 1.5, 2, 2.5, 3, 3.5, 4, 4.5, 5, 5.5, 6, 6.5, 7, 7.5, 8, 8.5, 9, 9.5, 10]
i write algorithm in provide target value, , in list of 2 (quantity, value) pairs returned such following rules followed. rules listed in decreasing order of importance, un-numbered rules being 'nice-to-have' note 'have-to-have'.
- the sum of products of quantity-value pairs equals target value
- either 1 or 2 quantity-value pairs used
- each pair in integer quantity , 1 of values list
- the sum of quantities minimized
- the 2 values within 2 of each other, such (value2 - value1) <= 2
- the number of 1/2 values minimized
- the lowest values possible in list used
my question follows: parameters of problem fall within of 'classic', or well-known/researched computer algorithms? if of conditions tweaked, problem made more 'classic' optimization problem?
i interested in approaching problem in other way 'brute force', knowledge of different optimization problems sparse.
edit
here examples:
#------example 1------------ print(find_combination(16.5)) # output = ({'qty':1, value:4.5}, # {'qty':2, value:6}) # following invalid because sum of qty # equivalent more half values used # output = ({'qty':3, value:5.5}) #------example 2------------ print(find_combination(15)) # output = ({'qty':3, value:5}) # following invalid because uses more half # values, , sum of quantity not @ least # 2 less above answer # output = ({'qty':2, value:7.5}) #------example 3------------ print(find_combination(12)) # output = ({'qty':2, 'value':6}) # following invalid because 2 values # not within 2 of each other. also, number of # different values not minimized # output = ({'qty':1, 'value':2}, {'qty':1, 'value':10})
does good:
largest = largest value in list if (target <= largest) { search in list, , maybe make sum of 2 elements if there's gap target } else { n = target / largest try larger n smaller values allowed set, check exact match. maybe clever remainder of target/largest avoid skip trial-divisions }
hmm, might start if didn't have other constraints, having quantities within 2 of each other.
using smallest values list conflicts "maintaining smallest sum of quantities". assume want smaller list values when doesn't increase sum of quantities compared candidate solution.
if target exact multiple of 1 of list values, rules don't should return single pair, assume goal. (the rules when target in set, quantity=1).
i'm going give now, until make clear rules are.
Comments
Post a Comment