There is an ordered array of integer elements and a limit. It is necessary to find the minimum possible and maximum possible sum that can greater or equal the limit, for the given elements.
The minimum sum is the minimum sum of the sequence greater or equal than limit
The maximum sum, is the sum of the sequence that satisfies the conditions, and gives the largest result
Conditions:
First Example:
arr = [100, 200, 300, 1000]
limit = 1000
The minimum here is 1000, because we can take 10 times 100 for example.
The maximum here is 1900, since we can take 100 + 200 + 300 + 300 + 1000.
Second Example:
arr = [3, 10, 15]
limit = 1000
The minimum here is 1000, because we can take 300 times 3 and 10 times 10.
The maximum here is 1014, since we can take 318 times 3 and 3 time 10 and 2 times 15
I wrote 1 algorithm based on recursion and one based on dynamic programming. Both the first and the second one produce incorrect results in certain situations
Example for Python:
from pprint import pprint
from typing import Tuple, List
import resource
import sys
resource.setrlimit(resource.RLIMIT_STACK, (0x10000000, resource.RLIM_INFINITY))
sys.setrecursionlimit(0x100000)
class CollectingRangeAnalyzer:
def __init__(self):
self.memo = {}
def recursion_method(self, pools: List[int], target_cap: int) -> Tuple[float, float]:
self._collect_helper(pools, target_cap, [], 0)
if not self.memo:
raise ValueError("No valid range found")
max_cap = max(self.memo)
min_cap = min(self.memo, key=lambda x: x if x >= target_cap else float("inf"))
return max_cap, min_cap
def _collect_helper(self, pools_, target_sum_, path, cur_sum):
if cur_sum >= target_sum_:
return
if self.memo.get(cur_sum):
return
for i, v in enumerate(pools_):
cur_sum += v
path.append(v)
self._collect_helper(pools_, target_sum_, path, cur_sum)
self.memo[cur_sum] = True
cur_sum -= v
path.pop()
@staticmethod
def dynamic_method(arr, limit):
table = []
arr_size = len(arr)
n_cols = limit // arr[0] + 1
max_cap = float("-inf")
min_cap = float("inf")
for i in range(arr_size):
table.append([])
for j in range(n_cols):
table[i].append(0)
for i in range(arr_size):
for j in range(n_cols):
if i == 0 and arr[0] * (j + 1) <= limit + arr[i]:
table[i][j] = arr[i] * (j + 1)
elif i > j or j < 0:
table[i][j] = table[i - 1][j]
else:
diagonal_prev = table[i - 1][j - 1]
j_prev = table[i][j-1]
if diagonal_prev < limit:
table[i][j] = diagonal_prev + arr[i]
else:
table[i][j] = max(diagonal_prev, j_prev)
max_cap = max(table[i][j], max_cap)
min_cap = min(table[i][j], min_cap, key=lambda x: x if x >= limit else float("inf"))
return max_cap, min_cap
# First Example
first_analysis_class = CollectingRangeAnalyzer()
first_array = [100, 200, 300, 1000]
first_limit = 1000
rec_first = first_analysis_class.recursion_method(first_array, first_limit) # output: (1900, 1000) SUCCESS
dynamic_first = first_analysis_class.dynamic_method(first_array, first_limit) # output: (1900, 1000) SUCCESS
# But if added the 10000 in first_array and run again I'll get the wrong result in the recursion function.
#
# first_array = [100, 200, 300, 1000, 10000]
#
#
# rec_first = first_analysis_class.recursion_method(first_array, first_limit) # output: (10900, 1000) WRONG
# dynamic_first = first_analysis_class.dynamic_method(first_array, first_limit) # output: (1900, 1000) SUCCESS
# Second Example
second_analysis_class = CollectingRangeAnalyzer()
second_array = [3, 10, 15]
second_limit = 1000
rec_second = second_analysis_class.recursion_method(second_array, second_limit) # output: (1014, 1000) SUCCESS
dynamic_second = second_analysis_class.dynamic_method(second_array, second_limit) # output: (1012, 1000) WRONG
I assume that you need to always start at the beginning of your sequence. Your examples were still not clear on that. If that is true then this should work:
import heapq
def min_max_limit_sum (arr, limit):
# A path will be (idx_k, ...(idx_1, (idx_0, None))...)
# By (value, index): path
known = {}
# heap of (value, counter, (next_index, prev_path))
upcoming = [(0, 0, (0, None))]
counter = 1
best_min = limit + sum(arr)
min_path = None
best_max = limit - 1
max_path = None
# While there is stuff in the heap.
while len(upcoming):
value, _, next_path = heapq.heappop(upcoming)
i = next_path[0]
if (value, i) in known or len(arr) <= i:
# Filter out alternate routes, and running off the end of the sequence.
continue
else:
path = next_path[1]
known[(value, i)] = path
if value < limit:
value += arr[i]
heapq.heappush(upcoming, (value, counter, (i, next_path)))
heapq.heappush(upcoming, (value, counter, (i+1, next_path)))
counter += 1
else:
if value < best_min:
best_min = value
min_path = path
if best_max < value:
best_max = value
max_path = path
return (best_min, min_path, best_max, max_path)
print(min_max_limit_sum([100, 200, 300, 1000], 1000))
If the assumption is not true, just set upcoming to have an entry for every single index.