algorithm - 寻找最大可能的整数和/积组合

Question

给定一个总是以 1 开头的 N 个整数列表的输入，例如:1、4、2、3、5。和一些目标整数 T。

按顺序处理列表，算法决定是否将数字与当前分数相加或相乘，以实现最大可能的输出

例如:[输入] 1, 4, 2, 3, 5 T=40

1 + 4 = 5
5 * 2 = 10
10 * 3 = 30
30 + 5 = 35 which is < 40, so valid.

但是

1 * 4 = 4
4 * 2 = 8
8 * 3 = 24
24 * 5 = 120 which is > 40, so invalid.

我在用算法将其概念化时遇到了麻烦——我只是在寻找有关如何思考它或至多是伪代码的建议。我将如何编写代码？

我的第一直觉是将 +/* 视为 1/0，然后测试排列，例如 0000(我认为长度 == N-1)，然后是 0001，然后是 0011，然后是 0111，然后是 1111，然后是 1000 等等

但我不知道如何将其放入给定一般 N 个整数的伪代码中。任何帮助将不胜感激。

Answer 1

您可以使用递归来实现排列。 Python 代码如下:

MINIMUM = -2147483648
def solve(input, T, index, temp):
    # if negative value exists in input, remove below two lines
    if temp >= T:
        return MINIMUM
    if index == len(input):
        return temp

    ans0 = solve(input, T, index + 1, temp + input[index])
    ans1 = solve(input, T, index + 1, temp * input[index])
    return max(ans0, ans1)

print(solve([1, 4, 2, 3, 5], 40, 1, 1))

但是这个方法需要O(2^n)的时间复杂度。