arrays - 使用 6 种面额找零的快速算法 : Interview Practice

Question

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

问题:假设我们想找 D 美元。我们有一个包含 N 个元素的数组 A。面额作为美元值存在于数组中，但我们事先不知道确切的面额。然而，我们得到 0 < A[j] < 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)

输出:

Can make change: True

$3 x 4

$18 x 1

$20 x 1

---

编辑

以前的解决方案具有复杂性 O(n^6)。但实际上我们可以使用 memoization 使其更快(或者，我们换句话说，dynamic programming)。让我们对 A 数组进行排序，并将其中的每个数字重复 6 次，所以我们会得到类似于 A = [3, 3, 3, 3, 3, 3, 5, 5, ...]。现在让我们填充 3D 矩阵 M[,,]，其中 M[bills_num, i, d] 是 true iff 我们可以改变d 美元和 bills_num 账单从 A 数组的第 i 位置开始。结果将在单元格 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)