02773: 采药
dp, http://cs101.openjudge.cn/practice/02773
辰辰是个很有潜能、天资聪颖的孩子，他的梦想是称为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
如果你是辰辰，你能完成这个任务吗？
输入
输入的第一行有两个整数T（1 <= T <= 1000）和M（1 <= M <= 100），T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的的整数，分别表示采摘某株草药的时间和这株草药的价值。
输出
输出只包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。
样例输入
70 3
71 100
69 1
1 2样例输出
3来源：NOIP 2005
解题思路：0-1背包问题(Knapsack problem)。内层循环（列）时间T，外层循环（行）药草M。
图解，可以参照《算法图解》，作何：Aditya Bhargava，译者：袁国忠。2016年出版。
T, M = map(int, input().split())
dp = [ [0] + [0]*T for _ in range(M+1)]
t = [0]
v = [0]
for i in range(M):
ti, vi = map(int, input().split())
t.append(ti)
v.append(vi)
for i in range(1, M+1): # 外层循环（行）药草M
for j in range(0, T+1): # 内层循环（列）时间T
if j >= t[i]:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-t[i]] + v[i])
else:
dp[i][j] = dp[i-1][j]
print(dp[M][T])空间优化的一维数组解法
T,M = map(int,input().split())
herb = []
for i in range(M):
herb.append([int(x) for x in input().split()])
dp=[0]*(T+1)
for i in range(M):
for j in range(T,0,-1):
if j >= herb[i][0]:
dp[j] = max(dp[j],dp[j-herb[i][0]]+herb[i][1])
print(dp[-1])2021fall-cs101，陈飞宇。
背包问题的空间优化写法：事实上创建dp 时不需要用二维列表存储每增加一行数据时的所有运算结果。只需要开一个last_data 的一维列表记录“上一行”数据的运算结果即可；前面各行的数据可以丢弃。因为在背包问题的状态转移方程中只需要用到“上一行”的运算结果和当前的输入数据。
#T 采药总时间，M 草药数目
T,M = map(int,input().split())
#dp[j]用于存储当采药总时间为j 时，由目前已给出的草药数据可采得的最大价值
dp = [0]*(T+1)
last_data = list(dp)
#外层循环遍历草药数据（M）
for i in range(M):
time,value = map(int,input().split())
#内层循环遍历采药时间（T）
for j in range(1,T+1):
if j >= time:
dp[j] = max(last_data[j],value + last_data[j-time])
else:
dp[j] = last_data[j]
#用last_data 将本次运算结果存起来以供下一次循环运算使用
last_data = list(dp)
print(dp[-1])记忆式搜索
import math
from functools import lru_cache
@lru_cache(maxsize = None)
def fn(i, s):
# i-th item, knapsack with available capacity s
if (s < 0):
return -math.inf
if (i == len(vs)):
return 0
return max(fn(i+1, s), vs[i] + fn(i+1, s-ws[i]))
T, M = map(int, input().split())
ws = []
vs = []
for _ in range(M):
t, v = map(int, input().split())
ws.append(t)
vs.append(v)
print(fn(0, T))T,M = map(int, input().split())
herb = []
for i in range(M):
herb.append([int(x) for x in input().split()])
dp=[0]*(T+1)
for i in range(M):
for j in range(T, herb[i][0] - 1, -1):
if j >= herb[i][0]:
dp[j] = max(dp[j], dp[j-herb[i][0]]+herb[i][1])
print(dp[-1])#T 采药总时间，M 草药数目
T,M = map(int,input().split())
#dp[j]用于存储当采药总时间为j 时，由目前已给出的草药数据可采得的最大价值
dp = [0]*(T+1)
last_data = list(dp)
#外层循环遍历草药数据（M）
for i in range(M):
time,value = map(int,input().split())
#内层循环遍历采药时间（T）
for j in range(1,T+1):
if j >= time:
dp[j] = max(last_data[j],value + last_data[j-time])
else:
dp[j] = last_data[j]
#用last_data 将本次运算结果存起来以供下一次循环运算使用
last_data = list(dp)
print(dp[-1])import math
from functools import lru_cache
@lru_cache(maxsize = None)
def fn(i, s):
# i-th item, knapsack with available capacity s
if (s < 0):
return -math.inf
if (i == len(vs)):
return 0
return max(fn(i+1, s), vs[i] + fn(i+1, s-ws[i]))
T, M = map(int, input().split())
ws = []
vs = []
for _ in range(M):
t, v = map(int, input().split())
ws.append(t)
vs.append(v)
print(fn(0, T))一般来说01背包如果限制T求最大W，那么dp时求T处的最大w；但是也可以求W处的最小t，并且时刻保持t<=T，最后寻找最大的有t的W。由于W本身没有限制，无法像t一样从T往0枚举，故自设一个限制100*100（采药的数据），从10000往0枚举。
这题T<=1000，显然枚T更优，但如果数据很刁钻，比如T很大，那可能这种方法更有效。
# 官祺云 24
T, n = map(int, input().split())
t, w = [0] * n, [0] * n
for i in range(n):
t[i], w[i] = map(int, input().split())
dp = [float('inf')] * 10001
dp[0] = 0
for i in range(n):
for j in range(10000, w[i] - 1, -1):
if dp[j - w[i]] + t[i] <= T:
dp[j] = min(dp[j], dp[j - w[i]] + t[i])
for i in range(10000, -1, -1):
if dp[i] != float('inf'):
print(i)
break使用 二维数组 和 递归 + LRU Cache 来解决问题。
- 使用 二维数组 的方法：
如果你使用二维数组的动态规划方法，可以将状态转移视为 二维的背包问题。我们使用一个 dp[i][j] 数组来表示在前 i 个草药中，使用不超过 j 时间的最大价值。
动态规划转移方程：
dp[i][j]表示使用前i个草药，且时间不超过j时的最大价值。对于每个草药
(time, value)，有两种选择：
- 不采摘它，
dp[i][j] = dp[i-1][j]。 - 采摘它，
dp[i][j] = dp[i-1][j-time] + value，前提是j >= time。
- 不采摘它，
二维数组实现：
def max_value_with_2d_array(T, M, herbs):
# dp[i][j]表示前i个草药，时间不超过j时的最大价值
dp = [[0] * (T + 1) for _ in range(M + 1)]
for i in range(1, M + 1):
time, value = herbs[i - 1]
for j in range(T + 1):
# 不采摘当前草药
dp[i][j] = dp[i - 1][j]
# 采摘当前草药，前提是时间允许
if j >= time:
dp[i][j] = max(dp[i][j], dp[i - 1][j - time] + value)
return dp[M][T]
# 输入读取
T, M = map(int, input().split()) # 读取T和M
herbs = []
for _ in range(M):
time, value = map(int, input().split())
herbs.append((time, value))
# 计算并输出结果
print(max_value_with_2d_array(T, M, herbs))说明：
dp[i][j]：表示前i株草药，在总时间j内能获得的最大价值。- 如果不采摘第
i株草药，dp[i][j]就等于dp[i-1][j]。 - 如果采摘第
i株草药，且时间j足够，dp[i][j]就等于dp[i-1][j-time] + value。
最终的结果就是 dp[M][T]，即前 M 株草药，在总时间 T 内可以获得的最大价值。
时间复杂度：
- O(M * T)，其中
M是草药的数量，T是最大时间。
- 使用 递归 + LRU Cache 方法：
递归 + LRU Cache（最少最近使用缓存）是一种更灵活的解法，可以通过缓存中间计算的结果来避免重复计算。我们可以通过递归的方式，分别计算在某一时间限制下，是否选择某个草药，并且将结果缓存，以便重复使用。
递归思路：
对于每一株草药
(time, value)，我们有两种选择：
- 不选择 这株草药，计算剩余时间内能获得的最大价值。
- 选择 这株草药，计算剩余时间内能获得的最大价值。
递归的基本形式是 max_value(time_left, idx)，表示从第 idx 株草药开始，在剩余时间 time_left 内可以获得的最大价值。
递归 + LRU Cache 实现：
from functools import lru_cache
def max_value_with_recursion(T, M, herbs):
@lru_cache(None)
def helper(time_left, idx):
if idx == M: # 如果已经考虑完所有草药
return 0
time, value = herbs[idx]
# 选择不采摘这株草药
max_val = helper(time_left, idx + 1)
# 选择采摘这株草药（前提是时间足够）
if time_left >= time:
max_val = max(max_val, helper(time_left - time, idx + 1) + value)
return max_val
return helper(T, 0)
# 输入读取
T, M = map(int, input().split()) # 读取T和M
herbs = []
for _ in range(M):
time, value = map(int, input().split())
herbs.append((time, value))
# 计算并输出结果
print(max_value_with_recursion(T, M, herbs))说明：
helper(time_left, idx)：从草药idx开始，剩余时间为time_left，返回能获得的最大价值。- 缓存机制：使用
@lru_cache(None)来缓存函数的计算结果，避免重复计算相同状态。 - 如果剩余时间不够，就跳过当前草药，递归处理下一个草药；如果可以采摘，则递归计算剩余时间内能获得的最大价值。
时间复杂度：
- O(M * T)，其中
M是草药的数量，T是最大时间，虽然有递归调用，但缓存机制使得每个状态只会被计算一次。
总结：
- 二维数组方法：适合传统的动态规划，使用
dp[i][j]来表示前i个草药，使用不超过j时间的最大价值。 - 递归 + LRU Cache 方法：适合用递归思想求解，并通过缓存机制避免重复计算，适合不需要显式构造 DP 数组的情况。
对于这个问题，使用动态规划是最常见的解法，而递归 + LRU Cache 更加灵活，适合递归式问题的求解。