采药问题属于01背包问题

采用动态规划进行求解：

• 保存结果：dp[i][j]表示前i件物品放入容量为j的背包，所能带来的最大价值
• 递推公式：①如果第i件物品不放入背包，那么就代表我们要放的是前i - 1件物品 => dp[i][j] = dp[i - 1][j]；②如果第i件物品放入背包，那么第i件物品的价值value[i]我已经获得了，除此以外，我还有j - weight[i]的空间可以放我们的前i - 1件物品；综上，可得递推公式为dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]
• 空间优化：注意到上面的递推公式中，dp[i - 1]是固定不动的，因此优化成dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
• 注意：因为j - weight[i]小于j，为了避免在访问dp[j]之前，dp[j - weight[i]]已被修改，我们需要倒序遍历
• 最终解为：dp[m](m为背包总容量，下标范围我们设置为[0, m]

def medicineCollection():
    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): # 逆序遍历的范围为[m, weight[i]]
                    dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
            print(dp[m])
        except (EOFError, KeyboardInterrupt):
            break
            
if __name__ == '__main__':
    medicineCollection()