📢📢📢📣📣📣
🌻🌻🌻Hello，大家好我叫是Dream呀，一个有趣的Python博主，多多关照😜😜😜
🏅🏅🏅2021年度博客之星TOP100,2021年度博客之星领域TOP5，Python领域优质创作者，欢迎大家找我合作学习（文末有VX 想进学习交流群or学习资料 欢迎+++）
💕入门须知：这片乐园从不缺乏天才，努力才是你的最终入场券！🚀🚀🚀
💓最后，愿我们都能在看不到的地方闪闪发光，一起加油进步🍺🍺🍺
🍉🍉🍉“一万次悲伤，依然会有Dream，我一直在最温暖的地方等你”，唱的就是我！哈哈哈~🌈🌈🌈
🌟🌟🌟✨✨✨

前言：【Python训练营】是针对Python语言学习所打造的一场刷题狂欢party！ 对基础知识把握不牢固的话，欢迎参考此套课程：Python公开课 搭配使用最佳嗷~喜欢的话就抓紧订阅起来吧！🍋🍋🍋如果对学习没有自制力或者没有一起学习交流的动力，欢迎私信或者在文末添加我的VX，我会拉你进学习交流群，我们一起交流学习，报团打卡

@TOC

题目描述

题目描述
小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有 N 种蒸笼，其中第 i 种蒸笼恰好能放 A个包子。每种蒸笼都有非常多笼，可以认为是无限笼。

每当有顾客想买 X 个包子，卖包子的大叔就会迅速选出若干笼包子来，使得这若干笼中恰好一共有 X 个包子。比如一共有 3 种蒸笼，分别能放 3、4 和 5 个包子。当顾客想买 11 个包子时，大叔就会选 2 笼 3 个的再加 1 笼 5 个的（也可能选出 1 笼 3 个的再加 2 笼 4 个的）。

当然有时包子大叔无论如何也凑不出顾客想买的数量。比如一共有 3 种蒸笼，分别能放 4、5 和 6 个包子。而顾客想买 7 个包子时，大叔就凑不出来了。

小明想知道一共有多少种数目是包子大叔凑不出来的。

输入描述
第一行包含一个整数 N(1≤N≤100)。

以下 N 行每行包含一个整数 A，（1≤A ≤100)。

输出描述
一个整数代表答案。如果凑不出的数目有无限多个，输出 INF。

输入输出样例

示例 1
输入
2
4
5

输出
6

样例说明
凑不出的数目包括：1, 2, 3, 6, 7, 11。

示例 2
输入
2
4
6

输出
INF

样例说明
所有奇数都凑不出来，所以有无限多个

运行限制
最大运行时间：1s
最大运行内存: 256M

解题思路

• 首先输入笼子数目，然后考虑换行输入多个数据即每一个笼子中的包子数；
• 利用math模块中求最大公约数gcd（）函数的求得笼子中的小笼包数量的最大公约数，若不为1，则说明其肯定有一种组合是无法表示的，固有无限可能，需要输出INF
• 使用完全背包算法求解不能表示的数，并将第一个数标记为1：dp[0] = 1
• 状态转移方程式：dp[j] = max(dp[j],dp[j-a[i]]) j-a[i]相当于反向从10000开始递减单个笼子的数量，从而达到单个倍数的可能性，并给可以取到的数标记为1，对于组合数，比如3，4，5、7咱们有是如何取到的呢？ dp[7]=0,但是dp[7-a[i]]=dp[7-4]=dp[3]=1,也就是说这个数可以被第一个数和第二个数相加得到，因此也可以被标记

源码分享

import math
N = 10000
dp = [0 for i in range(N)]
n = int(input())  # n 为第几个笼子
a = [int(input()) for j in range(n)]  # 循环输入每个笼子中的小笼包数量
g = a[0]
for i in range(n):
    g = math.gcd(g,a[i])  # 求得笼子中的小笼包数量的最大公约数，若不为1，则说明其肯定有一种组合是无法表示的，固有无限可能，需要输出INF
if g == 1:  #  使用完全背包算法求解不能表示的数
    dp[0] = 1  # 将第一个数标记为1
    for i in range(n):  # 有几种笼子的类型就遍历几种
        for j in range(a[i],N):  # a[i]对应的是笼子中的小笼包数量
            dp[j] = max(dp[j],dp[j-a[i]])  # 状态转移方程式，j-a[i]相当于反向从10000开始递减单个笼子的数量，从而达到单个倍数的可能性，并给可以取到的数标记为1
            # 对于组合数，比如3，4，5、7咱们又是如何取得到的呢？ dp[7]=0,但是dp[7-a[i]]=dp[7-4]=dp[3]=1,也就是说这个数可以被第一个数和第二个数相加得到，因此也可以被标记
    print(N-sum(dp))

学习总结

1.多行输入方法，并且将结果以列表方式进行存储：a = [int(input()) for j in range(n)]
2.完全背包问题，这个题目中便需要我们用0或者1去表示无和有，出现有便让其为1，开始前我们需要让dp列表中的第一项为1，从第一项中开始，以此去找遍历后的每一项看看能否表示出来，在dp列表其遍历的数据的本身序列或者本身减去开始前遍历的原始数据在dp中都有一个值可以表示，那此时遍历后的数据本身dp的值则有1取1，没1则为0.

🏅今天是我在Python训练营的第 24 天，希望每天都能见到最棒的你🏅

🌲🌲🌲 好啦，这就是今天要分享给大家的全部内容了
❤️❤️❤️如果你喜欢的话，就不要吝惜你的一键三连了~