查找整数的最大可能总和/乘积组合

Question

给定N个整数列表的输入始终以1开头,例如:1,4,2,3,5.并且一些目标整数为T.

按顺序处理列表,算法决定是否按当前分数添加或乘以数字以实现最大可能输出<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)时间复杂度.