用火柴棒拼出最大整数 - 算法题解

思路：由于数字字符需要的火柴棒数量是固定的，而且最多只能拼十个，因此我们可以先计算出每个数字字符最多能拼几个，并按照需要火柴棒数量从大到小排序。然后从需要火柴棒数量最多的数字字符开始，尽可能多地拼凑出整数的每一位，直到无法再拼出一位为止。最后输出拼出的整数即可。

代码实现：

matchsticks = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]  # 每个数字字符需要的火柴棒数量
max_nums = [0] * 10  # 每个数字字符最多能拼几个
for i in range(10):
    max_nums[i] = min(10, 300 // matchsticks[i])  # 最多拼几个
max_nums = [x for _, x in sorted(zip(matchsticks, max_nums), reverse=True)]  # 按照需要火柴棒数量从大到小排序

num = 0  # 拼出的整数
for i in range(9, -1, -1):  # 从需要火柴棒数量最多的数字字符开始
    while max_nums[i] > 0 and matchsticks[i] * max_nums[i] <= 300 - sum(matchsticks[j] * max_nums[j] for j in range(i)):  # 尽可能多地拼凑出整数的每一位
        num = num * 10 + i
        max_nums[i] -= 1

print(num)