【经典题目】01背包采药

原题链接，请戳这里

题目描述

       辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说: "孩子，这个山洞里有一些不同的草药， 采每一株都需要一 些时间， 每一株也有它自身的价值。 我会给你- -段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。如果你是辰辰，你能完成这个任务吗?

输入格式

第一行有2个整数T (1≤T≤1000)和M (1≤M≤100)，用一个空格隔开，T代表总共能够

用来采药的时间，M代表山洞里的草药的数目。

接下来的M行每行包括两个在1到100之间(包括1和100)的整数,分别表示采摘某株草药的时间和这株草药的价值。

输出格式

输出在规定时间内可以采到的药草的最大总价值。

输入输出样例：

输入：

70 3
71 100
69 1
1 2

输出：

3

数据范围：

· 对于30%的数据，M <= 10;

· 对于全部数据， M <= 100。

01背包参考题解

V, N = map(int, input().split())
dp = [0] * (V + 1)
for i in range(N):
    v, w = map(int, input().split()) # 体积和价值(权重)
    for j in range(V, v-1, -1):
        dp[j] = max(dp[j], dp[j-v] + w)
print(dp[V])

完全背包参考题解

V, N = map(int, input().split())
dp = [0] * (V + 1)
for i in range(N):
    v, w = map(int, input().split()) # 体积和价值(权重)
    for j in range(v, V+1):
        dp[j] = max(dp[j], dp[j-v] + w)
        print(dp[V])

【经典题目】完全背包疯狂的采药

原题链接，请戳这里

如果觉得有用，麻烦大家三连一下，谢谢！