0

I have a problem in which I have a 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 would like to write an algorithm in which I provide a target value, and in which a list of two (quantity, value) pairs is returned such that the following rules are followed. The rules are listed in decreasing order of importance, with un-numbered rules being 'nice-to-have' but note 'have-to-have'.

  1. The sum of all the products of the quantity-value pairs equals the target value
  2. Either one or two quantity-value pairs are used
  3. Each pair in an integer quantity and one of the values from the list
  4. The sum of quantities are be minimized
  5. The two values are within 2 of each other, such that (value2 - value1) <= 2

  • The number of 1/2 values are minimized
  • The lowest values possible in the list are used

My question is as follows: do the parameters of this problem fall within any of the 'classic', or well-known/researched computer algorithms? If some of the conditions were tweaked, could this problem be made to look more like a 'classic' optimization problem?

I am interested in approaching this problem in any other way than 'brute force', however my knowledge of different optimization problems is sparse.

Edit

Here are some examples:

#------Example 1------------
print(find_combination(16.5))
# output = ({'qty':1, value:4.5},
#           {'qty':2, value:6})
# The following is invalid because the sum of qty is
# equivalent but more half values are used
# output = ({'qty':3, value:5.5})
#------Example 2------------
print(find_combination(15))
# output = ({'qty':3, value:5})
# The following is invalid because it uses more half
# values, and the sum of the quantity is not at least
# two less than the above answer
# output = ({'qty':2, value:7.5})
#------Example 3------------
print(find_combination(12))
# output = ({'qty':2, 'value':6})
# The following is invalid because the two values are
# not within two of each other. Also, the number of
# different values was not minimized
# output = ({'qty':1, 'value':2},
            {'qty':1, 'value':10})
Improve this question
9
  • Could you give an example? I can't properly figure out what you're trying to do. Commented Sep 29, 2015 at 20:50
  • Do you have to return 2 pairs only? Or you meant any numbers of pairs as long as all pairs (quantity*value) adds up to to target value? Commented Sep 29, 2015 at 21:37
  • Well... This is far away from all the well-researched problems because it is not as minimal as these are. You have multiple objectives (for which some are more important than others). I would tackle it with Mixed-Integer-Programming, which should not be too hard. But careful/more precise modelling should be done first. Especially: which objectives are how important. Commented Sep 29, 2015 at 22:13
  • 1
    The more I look at your examples, the more they don't quite match what the list of rules says. 15 -> 3*5 is valid, but 2*7.5 isn't valid because the quantity is only one less than 3. It would have to be lower by two to outweigh <unspecified> other rule? The using-smaller-list-values rule? The rules say that doesn't outweigh using minimum quantities. Commented Sep 30, 2015 at 5:27
  • 1
    Your update still leaves the examples very confusing. ex2: what is the second part talking about? Total quantities not two less than the other case? ex3: "the number of different values was not minimized". Where is that objective mentioned in the rules? How much weight is placed on having only one value, compared to minimizing the sum of quantities? Your comment on my answer makes me think the example is wrong. Commented Sep 30, 2015 at 13:17

1 Answer 1

Reset to default
1

Does this do any good:

largest = largest value in the list
if (target <= largest) {
    search for it in the list, and maybe make a sum of two elements if there's a gap where the target would be
} else {
    n = target / largest
    try larger n with smaller values from the allowed set, to check for an exact match.
    Maybe do something clever with the remainder of target/largest to avoid skip some trial-divisions

}

Hmm, this might be a good start if you didn't have all those other constraints, like having quantities within 2 of each other.

Using the smallest values from the list conflicts with "maintaining the smallest sum of quantities". So I assume you only want to look for smaller list values when that doesn't increase the sum of quantities compared to another candidate solution.

If the target is an exact multiple of one of the list values, your rules don't even say that you should return a single pair, but I assume that is a goal. (The rules only say to do that when the target is actually in the set, with quantity=1).

I'm going to give up for now, until you make it clear what the rules actually are.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

You are correct in assuming that I only want to look for smaller list values when that does not increase the sum of quantities compared to other solutions. Also, addressing your third point, if the target is a multiple of one of the list values, that is a valid candidate, however typically there is an alternative solution using two list values that results in a smaller sum of quantities. I will try to think of a way of making this more clear in my original post.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.