01背包实战 - 最小邮票数

• 题目要求：给定不同面额的邮票，要求我们用最少的邮票数，达到指定的面值
• 求解思路：该题属于典型的01背包问题，因为给定邮票张数时，相同面额也认为是单独的一张，即只有0（不拿）和1（拿）两种状态 指定面值为我们的背包容量m，给定的邮票张数为我们的物品数量n，每张邮票的价值我们认为是相同的，需要注意的是，这里要求的是最小，而不是最大，因此 需要对递推公式进行修改，这里我们直接采用空间优化后的方法
• 递推公式：dp[j] = min(dp[j], dp[j - weight[i]] + value[i]
• 难点分析：①无解的判断：将dp数组初始化为无穷大，若最后dp[m]为无穷大，则说明无解，输出0即可，反之，输出dp[m]； ②确保背包完全放满：添加一条判断，if j == weight[i]: dp[j] = 1，其余情况再进行递推

def minStamps():
    while True:
        try:
            # m为背包容量（这里是指定的面值），n为物品数量（这里是给定的邮票张数）
            m, n = int(input()), int(input())
            # weight为物品对应的重量（这里是邮票的面值），value为物品对应的价值（这里是相同的，设为1）
            weight = [int(i) for i in input().split()]
            value = [1 for i in range(n)]
            inf = float('inf')
            dp = [inf for i in range(m + 1)]
            for i in range(n):
                for j in range(m, weight[i] - 1, -1):
                    if j == weight[i]:
                        dp[j] = 1
                    else:
                        dp[j] = min(dp[j], dp[j - weight[i]] + value[i])
            # dp[m]为无穷大，即无解
            if dp[m] == inf:
                print(0)
            else:
                print(dp[m])
        except (EOFError, KeyboardInterrupt):
            break


if __name__ == '__main__':
    minStamps()