1

办公用品商店以 5 支、8 支或 24 支的包装出售您最喜欢的钢笔类型。因此，例如，可以正好买 13 支钢笔（一包 5 支，第二包 8 支），但不可能正好买 11 支钢笔，因为没有 5 和 8 的非负整数组合和 24 加起来是 11。要确定是否有可能恰好购买 n 支笔，必须找到 a、b 和 c 的非负整数值，使得

5a + 8b + 24c = n

编写一个名为 numPens 的函数，该函数接受一个参数 n，如果可以购买 5、8 和 24 个包装单位的组合以使笔的总数恰好等于 n，则返回 True，否则返回 False。

注意：这是上个月的中期考试中出现的问题。我无法解决它，但仍在寻找解决方案。任何帮助都将被接受。python中的代码或解决它的算法。谢谢

4

1 回答 1

3

这听起来像是动态规划的一个很好的候选者。

def numPens(n):
  pen_sizes = [5, 8, 24]
  results = [True]
  for i in range(1, n+1):
    results.append(any(i >= size and results[i - size] for size in pen_sizes))
  return results[n]

这里的主要见解是：

  1. 可以实现 0 支笔（简单来说：每种尺寸 0 包）。
  2. 如果我们已经知道少于 n 笔的答案，我们就可以算出是否可以得到 n 笔。

例如，假设我们想知道我们是否可以得到 10 支钢笔，假设我们已经知道 0 到 9 的答案。好吧，我们至少需要一包才能做到这一点。那么有3种情况需要考虑：

  1. 一包 5 支以上，但如果可能的话，我们会得到 5 支钢笔。
  2. 一包 8 支以上，但我们会得到 2 支钢笔，如果有可能得到 2 支钢笔。
  3. 一包 24 支以上，但如果可能的话，我们会得到 -14 支笔，如果有可能的话。

最后一个是无意义的，所以当（且仅当）有可能得到 5 支或 2 支时，就有可能得到 10 支钢笔。因为我们假设我们已经知道 0 到 9 的答案，所以我们可以解决这个问题（事实证明，5 支笔是可能的，作为一包 5 支，所以我们得出结论，10 支也是如此）。

因此，为了让自己处于总是有较小 n 值的答案的情况，我们从 0 的明显答案开始。然后我们计算 1 的答案（因为我们已经有了 0 的答案，我们可以做这个）。然后我们计算 2 的答案（因为我们已经有 0 和 1，我们可以这样做），依此类推，直到我们得到我们想要的 n 的答案。

这段代码封装了先前结果的实际计算结果：True如果有任何包装尺寸size，购买该尺寸的包装是有意义的（没有得到负数i - size），它就会产生，我们之前发现一种买i - size笔的方法。

any(i >= size and results[i - size] for size in pen_sizes)

其余代码只是让我们将该结果存储在results列表中以供将来使用，并最终返回最终结果。

于 2013-04-21T19:31:50.377 回答