Python程序：查找可以使用硬币凑成的最大连续值数量

假设我们有一个名为coins的数组，包含n个元素，它表示我们拥有的硬币。第i个硬币的值表示为coins[i]。如果我们可以选择一些硬币，使得它们的值之和等于x，那么我们就可以凑成值x。我们必须找到从0开始（包括0）可以获得的最大连续值的数量。

因此，如果输入类似coins = [1,1,3,4]，则输出将为10，因为

• 0 = []

• 1 = [1]

• 2 = [1,1]

• 3 = [3]

• 4 = [4]

• 5 = [4,1]

• 6 = [4,1,1]

• 7 = [4,3]

• 8 = [4,3,1]

• 9 = [4,3,1,1]

为了解决这个问题，我们将遵循以下步骤：

• 对列表coins进行排序

• ans := 1

• 对于coins中的每个硬币，执行以下操作：

  • 如果coin > ans，则

    • 退出循环

  • ans := ans + coin

• 返回ans

示例

让我们看看下面的实现来更好地理解：

def solve(coins):
   coins.sort()
   ans = 1
   for coin in coins:
      if coin > ans:
         break
      ans+=coin
   return ans

coins = [1,1,3,4]
print(solve(coins))

输入

[1,1,3,4]

输出

10

Arnab Chakraborty

更新于: 2021年10月7日

385 次浏览

开启您的 职业生涯

通过完成课程获得认证

开始学习