Interval Subset Sum X56351


Statement
 

pdf   zip

html

We consider a relaxed version of the standard Subset Sum problem (like in, e.g., P40685). However, in this problem, instead of a goal sum, we are provided a lower bound L and an upper bound U, and we are to add up values from a list t so that the sum falls between them.

More precisely, given are: a lower limit L, an upper limit U, and a sequence t consisting of n values. Here n is a non-negative integer, and all the other values are positive integers. Solutions are subsets (rather, more precisely, subsequences) of t whose sum falls in the interval [L, U) (closed at the left and open at the right: this should sound usual to pythonistas). Thus, you are asked to write a function sub_sum_interval(L, U, t) that returns a list of values taken from t that is as short as possible, and whose sum is at least L and strictly smaller than U. The solution may have repeated values only if they are already repeated in the given sequence.

Note that solutions are always nonempty (why?); if no solution exists, your function should signal that by returning an empty list.

Observation

Often there will be several solutions: your function may return any solution that fulfills the given conditions. On the other hand, the time allowance of this problem is rather mild, and even quite inefficient solutions may be accepted.

Sample session 
>>> sol = sub_sum_interval(96, 104, [60, 15, 25, 95, 80, 5, 10, 5, 10, 75])
>>> print('Sum in interval [ 96 ,  104 ): ', 96  <= sum(sol) <  104 )
Sum in interval [ 96 ,  104 ):  True
>>> print(len(sol))
2
>>> sol = sub_sum_interval(10, 20, [55, 55])
>>> print('Sum in interval [ 10 ,  20 ): ', 10  <= sum(sol) <  20 )
Sum in interval [ 10 ,  20 ):  False
>>> print(len(sol))
0
>>> sol = sub_sum_interval(40, 40, [25, 15])
>>> print('Sum in interval [ 40 ,  40 ): ', 40  <= sum(sol) <  40 )
Sum in interval [ 40 ,  40 ):  False
>>> print(len(sol))
0
>>> sol = sub_sum_interval(30, 40, [5, 5, 5, 5, 5, 10])
>>> print('Sum in interval [ 30 ,  40 ): ', 30  <= sum(sol) <  40 )
Sum in interval [ 30 ,  40 ):  True
>>> print(len(sol))
5
>>> sol = sub_sum_interval(30, 40, [20, 20])
>>> print('Sum in interval [ 30 ,  40 ): ', 30  <= sum(sol) <  40 )
Sum in interval [ 30 ,  40 ):  False
>>> print(len(sol))
0
Information
Author
José Luis Balcázar
Language
English
Official solutions
Python
User solutions
Python