有序整数数组的最小/最大达标和求解：递归与DP算法问题排查

给定一个有序整数数组和一个limit，需找出满足条件的、大于等于limit的最小可能和与最大可能和：

• 最小和：≥limit的最小序列和
• 最大和：满足条件的最大序列和

约束条件 #

• 序列中的元素可重复使用，例如可选取101+101+201+201
• 求和时不可跳过数组元素，例如不能直接选取101+301，必须按顺序选取101+201+301
• 一旦求和达到limit，即可停止后续操作

示例 #

示例1 #

arr = [100, 200, 300, 1000]，limit = 1000

• 最小和为1000（如选取10次100）
• 最大和为1900（如选取100+200+300+300+1000）

示例2 #

arr = [3, 10, 15]，limit = 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

测试问题说明 #

1. 递归方法问题：当数组添加10000后，递归方法输出最大和为10900，正确结果应为1900
2. 动态规划方法问题：处理示例2时，输出最大和为1012，正确结果应为1014

内容的提问来源于stack exchange，提问作者Aleksey