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'.

  1. the sum of products of quantity-value pairs equals target value
  2. either 1 or 2 quantity-value pairs used
  3. each pair in integer quantity , 1 of values list
  4. the sum of quantities minimized
  5. 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

Popular posts from this blog

html - Outlook 2010 Anchor (url/address/link) -

javascript - Why does running this loop 9 times take 100x longer than running it 8 times? -

Getting gateway time-out Rails app with Nginx + Puma running on Digital Ocean -