21458: 健身房

dp，http://cs101.openjudge.cn/routine/21458/

小嘤是大不列颠及北爱尔兰联合王国大力士，为了完成增肌计划，他需要选择一些训练组进行训练：有n个训练组，每天做第i个训练需要耗费ti分钟，每天坚持做第i个训练一个月后预计可增肌wi千克。因为会导致效果变差，小嘤一天不会做相同的训练组多次。由于小嘤是强迫症，他希望每天用于健身的时间恰好为T 分钟，他希望在一个月后获得最多的增肌量，请帮助小嘤计算：他训练一个月后最大增肌量是多少呢？

对应英文描述：

Boingo, a bodybuilder from the United Kingdom of Great Britain and Northern Ireland, needs to choose a number of training sets in order to complete his muscle building program: there are n training groups, and it takes ti minutes per day to do the i-th training set, and It's expected to gain wi kilograms of muscle after doing the first i training set every day for one month. Boingo would not do the same training set more than once a day because it's not effective. Since Boingo is obsessive-compulsive, he wants to spend exactly t minutes per day working out, he wants to gain the maximum amount of muscle mass after one month of training, please help him.

输入

第一行两个整数 T,n。

第 2 行到第 n+1 行，每行两个整数 ti,wi。

保证 0 < ti ≤ T ≤ 10^3, 0 < n ≤ 10^3, 0 < wi < 20。

输出

如果不存在满足条件的训练计划，输出-1。

如果存在满足条件的训练计划，输出一个整数，表示训练一个月后的最大增肌量。

样例输入

sample1 in
6 4
2 1
4 7
3 5
3 5

sample1 out
10

样例输出

sample2 in
700 4
450 5
340 1
690 10
9 2

sample2 out
-1
样例2解释：无法找出一种方案满足训练时间恰好等于T.

来源：cs101 2020 Final Exam

“恰好”型dp。类似方法：最开始的设为0，其余的都为设为负无穷。。。 https://zhuanlan.zhihu.com/p/560690993?utm_id=0

python

# 23n2300011031,黄源森
t,n=map(int,input().split())
dp=[0]+[-1]*(t+1)
for i in range(n):
    k,w=map(int,input().split())
    for j in range(t,k-1,-1):
        if dp[j-k]!=-1:
            dp[j]=max(dp[j-k]+w,dp[j])
print(dp[t])

01恰好背包

python

def max_muscle_gain(T, n, trainings):
    # 定义一个很大的负数作为无效值
    INF = -10 ** 9

    # 初始化 dp 数组
    dp = [[INF] * (T + 1) for _ in range(n + 1)]

    # 设置初始条件
    for i in range(n + 1):
        dp[i][0] = 0  # 时间为 0 时，增肌量为 0

    # 动态规划转移
    for i in range(1, n + 1):
        ti, wi = trainings[i - 1]
        for j in range(T + 1):
            dp[i][j] = dp[i - 1][j]  # 不选择第 i 个训练组
            if j >= ti:
                dp[i][j] = max(dp[i][j], dp[i - 1][j - ti] + wi)  # 选择第 i 个训练组

    # 输出结果
    if dp[n][T] < 0:
        return -1
    else:
        return dp[n][T]


# 读取输入
T, n = map(int, input().split())
trainings = [tuple(map(int, input().split())) for _ in range(n)]

# 计算并输出结果
result = max_muscle_gain(T, n, trainings)
print(result)

明确状态定义是动态规划（DP）问题的关键步骤之一。状态定义直接影响到初始化和状态转移方程的设计。下面我详细解释一下如何通过状态定义来指导初始化和状态转移。
状态定义
首先，我们需要明确 dp 数组的含义。在这个问题中，我们可以定义 dp[i][j] 为从前 i 个训练组中选择若干个训练组，并且总时间为 j 时的最大增肌量。
初始化
根据状态定义，我们需要初始化 dp 数组的边界条件：
dp[0][j] = -INF，当没有训练组可以选择时，任何非零时间的增肌量都应该是无效的（用 -INF 表示）。
dp[i][0] = 0，当时间为 0 时，无论有多少训练组，增肌量都是 0。
状态转移方程
状态转移方程描述了如何从已知状态推导出新状态。在这个问题中，对于每个训练组 i 和时间 j，有两种选择：
不选择第 i 个训练组，此时 dp[i][j] = dp[i-1][j]。
选择第 i 个训练组，此时 dp[i][j] = dp[i-1][j-t[i]] + w[i]，前提是 j >= t[i]。

python

#等价于必须装满的01背包问题  渠成锐
t,n=map(int,input().split())
dp=[[0]+[-1]*(t+1000) for i in range(n)]
#+1000是为了防止负向索引 
#第1列为0，表示背包大小为0时的合法解均为0
wl=[]#重量，也即用时
vl=[]#价值，也即增肌量
for _ in range(n):
    a,b=map(int,input().split())
    wl.append(a)
    vl.append(b)
for i in range(n):
    w=wl[i]
    v=vl[i]
    for j in range(1,t+1):
        if dp[i-1][j-w]>=0:#如果子问题的解合法
            dp[i][j]=max(dp[i-1][j-w]+v,dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j]#不合法则继承上一行的状态
print(dp[n-1][t])

python

T, n = map(int, input().split())
dp = [ ([0] + [-1]*T) for _ in range(n + 1)]

t = [0]
w = [0]
for i in range(n):
        ti, wi = map(int, input().split())
        t.append(ti)
        w.append(wi)

for i in range(1, n+1):
        for j in range(0, T+1):
                if j >= t[i] and dp[i - 1][j - t[i]] != -1:
                        dp[i][j] = max(dp[i-1][j], dp[i-1][j-t[i]] + w[i])
                else:
                        dp[i][j] = dp[i-1][j]

print(dp[n][T])

21458: 健身房 ​

21458: 健身房