点菜问题属于背包问题中的01背包

• 物品是一个整体，两个状态，放或不放，因此得名01背包

• 有n个物品，背包容量为m，每个物品有重量w和价值v，要求放入背包中的物品价值最大

• 保存结果：dp[i][j]表示前i个物品放入容量为j的背包的最大价值

• 递推起点：dp[0][j] = dp[i][0] = 0（同时也是边界值）

• 递推公式：①如果第i件物品放进去，背包剩余容量为j - w[i] => dp[i][j] = dp[i - 1][j - w[i]] + v[i]; ②如果第i件物品不放进去，背包剩余容量为j => dp[i][j] = dp[i - 1][j]; 综合①②可以得出我们的解result = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i])

• 补充：从result中可以看出，dp[i - 1]是不变的，因此我们可以将result的形式修改为 => result = max(dp[j], dp[j - w[i]] + v[i])。但是因为j - w[i] < j，为了避免在确定dp[j]时，dp[j - w[i]]已被更新，所以我们需要倒序遍历j

• 最终解为：dp[m]（dp初始化时范围设为[0,m]）

def order():
    while True:
        try:
            list = [int(i) for i in input().split()]
            # m为背包容量（这里是手上有多少钱），n为物品数量（这里是能点几个菜）
            m, n = list[0], list[1]
            # weight为物品需要占用的背包容量（这里是价格），value为物品对应的价值（这里是可口程度）
            weight = []
            value = []
            for i in range(n):
                list = [int(j) for j in input().split()]
                weight.append(list[0])
                value.append(list[1])
            dp = [0 for i in range(m + 1)]  # dp的范围为[0, m]
            for i in range(n):
                for j in range(m, weight[i] - 1, -1):
                    dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
            print(dp[m])
        except (EOFError, KeyboardInterrupt):
            break


if __name__ == '__main__':
    order()