算法
(DP,背包问题) $O(nm)$
经典01背包问题。
采药总时间相当于背包容量,每一株药相当于一件物品,采药时间相当于该物品的体积,草药的价值相当于物品价值。
时间复杂度
01背包问题的时间复杂度等于 物品数量 × 背包容量,因此本题的时间复杂度是 $O(nm)$。
C++ 代码
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int m, n;
int f[N];
int main()
{
cin >> m >> n;
for (int i = 0; i < n; i ++ )
{
int v, w;
cin >> v >> w;
for (int j = m; j >= v; j -- )
f[j] = max(f[j], f[j - v] + w);
}
cout << f[m] << endl;
return 0;
}
f[j]表示什么?
背包容量为j(时间为j)最大可以装的价值。可以参考b站视频 https://www.bilibili.com/video/BV1K4411X766/?spm_id_from=333.337.search-card.all.click&vd_source=dc097a8d97c19248a89ac1695b98201e
thank you
感谢
原来也可以不用建v[i]和w[i]..