六种面额变化的快速算法:面试实践

Question

我找到了这个问题的解决方案，但它需要O(n^2)。有可能做得更好吗？

问题:假设我们想找D美元的零钱。我们有一个含有N个元素的数组A。这些面额以美元值的形式存在于数组中，但我们不知道确切的高级面额。然而，我们得到了0< Aj < 125*N的限制条件是，我们每种面额中只有6种面额，我们必须能够确定我们是否可以使用精确地给出6总钞票(我们可以重复纸币并假定票据是任何类型的，所以我们可以有4美元纸币)。

如果A= 3,4,6,5,20,18,10,30和D= 50。然后，该算法返回自5+5+5+5+10+20以来的true。

我的尝试：

我试着排序然后再除法，但后来我陷入困境，因为我不知道如何消除可能的选择，因为我不知道数组中的确切内容。更好的是，如果没有在O(n^2)时间内显式地进行，我不知道如何肯定地说它是不可能的。我知道我被限制在6张钞票上，这有可能利用这个事实吗？

Answer 1

在我看来，这是一个典型的递归问题。让我们编写一个函数，检查我们是否可以对D美元进行更改。为此，我们将取第一张钞票(假设是3美元)，从D中删除它，然后递归地检查是否可以对D - 3美元进行更改。

如果我们不检查我们已经检查过的组合，我们可以更快地解决这个问题。因此，如果我们已经知道账单3, 5, 10不适合我们的需要，那么我们也不需要检查组合5, 10, 3。为此，我们首先需要对A数组进行排序，然后将最后使用的票据数(last_bill_id)传递给check函数。在函数中，我们不需要检查数字小于last_bill_id的任何组合。

python中的完整解决方案：

A = [3, 4, 6, 5, 20, 18, 10, 30]
D = 50


def check(counters, current_sum, depth, last_bill_id):
    global A
    if depth > 6:  # max amount of bills is 6
        return False
    if depth == 6:  # we used 6 bill, did we get the correct sum?
        return current_sum == 0
    if current_sum <= 0:  # we gave too much change
        return False
    # current_sum > 0 and depth < 6
    for i in xrange(last_bill_id, len(A)):
        if counters[i] < 6:
            # we can use i-th bill another time
            counters[i] += 1
            if check(counters, current_sum - A[i], depth + 1, i):
                return True
            counters[i] -= 1
    return False


# init counters with zeros
counters = [0] * len(A)
# check if we can change for `D`
A = sorted(A)  # sort A before the function
print 'Can make change:', check(counters, D, 0, 0)
# print bills with counters
for i, c in enumerate(counters):
    if c > 0:
        print '$%d x %d' % (A[i], c)

输出：

可以做出改变:真的 $3x4 $18x1 $20x1

编辑

以前的解决方案具有复杂性O(n^6)。但是实际上，我们可以使用回忆录 (或者，我们用另一种方式，动态规划)使它变得更快。让我们对A数组进行排序，并将其中的每个数字重复6次，这样我们就可以得到类似于A = [3, 3, 3, 3, 3, 3, 5, 5, ...]的内容。现在让我们填充3D矩阵M[,,]，其中M[bills_num, i, d]是true当且仅当我们可以用从A数组的i-th位置开始的bills_num票据对d美元进行更改。结果将出现在单元格M[6, 0, D]中。该矩阵的大小为6 x (6 * n) x D，因此我们可以在O(6 * (6 * n) * D) == O(n * D)时间内填充它(使用类似于前面的解决方案的递归方法)。python的代码：

A = [3, 4, 6, 5, 20, 18, 10, 30]
D = 50

# sort A and repeat 6 times
A = sorted(A * 6)
# create matrix M, where:
# 0 == uncomputed, 1 == True, -1 == False
arr1d = lambda x: [0] * x
arr2d = lambda x, y: [arr1d(y) for i in xrange(x)]
arr3d = lambda x, y, z: [arr2d(y, z) for i in xrange(x)]
M = arr3d(6 + 1, len(A), D + 1)


def fill_m(bills_num, start_pos, d):
    global A, M
    if d == 0:  # can make change for 0 only with 0 bills
        return True if bills_num == 0 else False
    if d < 0 or bills_num <= 0 or start_pos >= len(A):
        return False
    if M[bills_num][start_pos][d] == 0:
        # need to compute cell value
        if fill_m(bills_num, start_pos + 1, d):
            M[bills_num][start_pos][d] = 1
        elif fill_m(bills_num - 1, start_pos + 1, d - A[start_pos]):
            M[bills_num][start_pos][d] = 1
        else:
            M[bills_num][start_pos][d] = -1
    return M[bills_num][start_pos][d] == 1


print 'Can make change for $', D, fill_m(6, 0, D)