有一个整数元素的有序数组和一个限制。对于给定的元素，有必要找到可以大于或等于 limit 的最小可能和最大可能总和。
最小和是大于或等于limit
的序列的最小和最大和，是满足条件的序列之和，并给出最大的结果
条件：
第一个例子：
arr = [100, 200, 300, 1000]
限制=1000
这里的最小值是1000，因为我们可以拿10乘以100来举例。
这里的最大值是 1900，因为我们可以取 100 + 200 + 300 + 300 + 1000。
第二个例子：
arr = [3, 10, 15]
限制=1000
这里的最小值是 1000，因为我们可以取 300 乘以 3 和 10 乘以 10。
这里的最大值是 1014，因为我们可以取 318 乘以 3 和 3 乘以 10 以及 2 乘以 15
我写了一种基于递归的算法和一种基于动态规划的算法。在某些情况下，第一个和第二个都会产生错误的结果
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
我认为您需要始终从序列的开头开始。你的例子仍然不清楚。如果这是真的，那么这应该有效：
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))
如果假设不成立，只需设置
upcoming