Luogu P1616 疯狂的采药 解题报告

题目链接:P1616 疯狂的采药

题目分析:

很明显的完全背包。

首先,我们先把这道题转化为标准完全背包:

各种草药 物品
草药的价值 物品的价值
草药的采摘时间 物品的质量
总采摘时间 背包容量

ok,那么这道题就变成了板子题。

我们先来设计状态


$$\text{dp[i]为背包容量为i时,能放下的物品的最大价值}$$

$$\text{t[j]与p[j]分别存储第j个物品的质量和价值}$$

然后进行状态转移

对于容量为k的背包,第m个物品,我们考虑:

如果放这件物品,那么k容量背包的价值为dp[k-t[m]]+p[m]

如果不放,那么k容量背包的价值仍为原始的dp[k]

根据数组dp的定义,我们可以得到状态转移方程:

$$\text{dp[k]=max(dp[k-t[m]]+p[m],dp[k])}$$

同时,我们需要考虑该物品放入背包的先决条件:

$$\text{k-t[m]}\ge\text{0}$$

考虑每一件物品,并且综合上面的条件,我们得到了代码:

1
2
3
4
5
6
7
for(int i=1;i<=T;i++){
dp[i]=0;
//初始化,可通过将数组开在主函数外面省略这一步
for(int j=1;j<=n;j++){
if(i-t[j]>=0) dp[i]=max(dp[i],dp[i-t[j]]+p[j])
}
}

问题所求的便是dp[T]。

Source Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<cstdio>
#include<algorithm>
using std::max;
int main(){
int n,T;
scanf("%d%d",&T,&n);
int t[n+1],p[n+1],dp[T+1];
for(int i=1;i<=n;i++){
scanf("%d%d",&t[i],&p[i]);
}
dp[0]=0;
for(int i=1;i<=T;i++){
dp[i]=0;
for(int j=1;j<=n;j++){
if(i-t[j]>=0) dp[i]=max(dp[i],dp[i-t[j]]+p[j])
}
}
printf("%d",dp[T]);
return 0;
}
# DP
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×