题解采药P1048
2023z
·
·
题解
这个题目就是一个很水很水很水的 01 背包问题。
题意
简单来说就是让辰辰成为最伟大的医师在总时间内收集的药品总价值最大。
思路
首先，我们知道背包问题用贪心是不行的。我们举一个反例：背包的容量是 9 ，有 3 个物品，大小分别是 7 ， 4 ， 4 ，价值是 10 ， 6 ， 6 。显然，正确答案为 12 。而贪心按价值优先为 10 ，按性价比来同样也是 10 ，所以贪心法不成立。于是就开始 dp：那无非就是选和不选两种情况。我们用 f[i][j] 表示放入前 i 个物品用了 j 容量。
动态转移方程式：
**code**：
```cpp
#include<bits/stdc++.h> //万能头万岁QwQ
using namespace std;
struct med{
int t,v;
}a[110]; //t代表时间，v代表价值
int f[110][1010];
int t,m;
int main(){
cin>>t>>m;
for(int i=1;i<=m;i++) cin>>a[i].t>>a[i].v; //输入
for(int i=1;i<=m;i++){
for(int j=0;j<=t;j++){ //注意范围j要<=t
if(j>=a[i].t) f[i][j]=max(f[i-1][j-a[i].t]+a[i].v,f[i-1][j]); //if(j>=a[i])判断它是否可选，方程式如上
else f[i][j]=f[i-1][j];
}
}
cout<<f[m][t]; //输出
return 0;
} //本蒟蒻的第一篇题解，求过QWQ
```