动态规划思路详解-贪吃的大嘴

解题思路:

注意事项:

参考代码:

def find_cakes(cakes, m):
    # 初始化动态规划数组，dp[i][j]表示前i个小蛋糕中选择若干个，美味度之和为j所需的最小数量
    n = len(cakes)
    dp = [[float('inf')] * (m + 1) for _ in range(n + 1)]

    # 初始状态，前0个小蛋糕，美味度之和为0所需的数量为0
    for i in range(n + 1):
        dp[i][0] = 0

    # 动态规划递推
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            # 如果当前小蛋糕的美味度大于当前目标和，不选择当前小蛋糕
            if cakes[i - 1] > j:
                dp[i][j] = dp[i - 1][j]
            else:
                # 选择当前小蛋糕或者不选择，取最小值
                dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - cakes[i - 1]] + 1)

    # 如果最终的dp[n][m]仍然为inf，表示无法达到目标和
    if dp[n][m] == float('inf'):
        return "><"
    return dp[i][j]



a, b = map(int, input().strip().split())
obj = []
for i in range(b):
    m, n=map(int,input().strip().split())
    for j in range(n):
        obj.append(m)
cakes = obj
target_deliciousness = a
result = find_cakes(cakes, target_deliciousness)
print(result)