给定一个大小为 n 的数组。您必须使用 x 中的最小元素数获得一个总和，比如 x 并且该数组中的任何元素都可以无限使用

Question

有没有最优化的方法来解决这个问题。我有一种在 O(nx) 中解决它的方法，谁能建议我更好的解决方案。

Answer 1

这是一个称为 unbounded knapsack 的问题。这个问题的优化版本是 NP-hard，但是有伪多项式算法可以在 O(nx) 中解决它。

这是 Python 中的示例实现：

def solve(A, x):
    T = [float('inf')]*(x+1)
    T[0] = 0

    for element in A:
        for i in xrange(len(T)-element):
            T[i+element] = min(T[i+element], T[i]+1)

    return T[x]

print solve([5, 2], 10) #2: 5+5 = 10    
print solve([5, 2], 8)  #4: 2+2+2+2 = 8

此实现只是 returns 最少的元素数。寻找实际元素（单个组合，它们的数量可能呈指数级增长）留作练习。

给定一个大小为 n 的数组。您必须使用 x 中的最小元素数获得一个总和，比如 x 并且该数组中的任何元素都可以无限使用

Given an array of size n. You have to obtain a sum say x using minimum no of elements in x and any element in this array can be used infinitely

arrays

algorithm

dynamic