洛谷P1616题解：无限采摘的草药价值最大化（完全背包问题）

一、问题理解

题目给出：

• 总采药时间t

• 草药种类数m

• 每种草药的采摘时间a_i和价值b_i

要求计算在不超过总时间t的情况下，能够获得的最大草药价值总和。

二、算法选择

这是一个典型的完全背包问题，可以使用动态规划来解决。我们需要定义一个数组dp，其中dp[i]表示在时间i内能获得的最大价值。

三、优化思路

1. 空间优化：使用一维数组代替二维数组

2. 遍历顺序优化：正序遍历时间，允许重复选择同一物品

四、C++代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespACe std;

int main() {
    int t, m;
    cin >> t >> m;
    
    vector<int> time(m), value(m);
    for (int i = 0; i < m; ++i) {
        cin >> time[i] >> value[i];
    }
    
    vector<long long> dp(t + 1, 0);
    
    // 完全背包核心算法
    for (int i = 0; i < m; ++i) {
        for (int j = time[i]; j <= t; ++j) {
            dp[j] = max(dp[j], dp[j - time[i]] + value[i]);
        }
    }
    
    cout << dp[t] << endl;
    return 0;
}

五、代码解析

1. ‌输入处理‌：读取总时间t和草药种类数m，然后读取每种草药的时间和价值。

2. ‌DP数组初始化‌：创建大小为t+1的数组dp，初始化为0。

3. ‌完全背包处理‌：

• 外层循环遍历每种草药

• 内层循环从该草药的时间开始正序遍历到总时间t

• 更新dp[j]为不选当前草药和选当前草药两种情况的最大值

4. ‌输出结果‌：dp[t]即为所求的最大价值

六、扩展思考

1. 如何记录选择的草药种类和数量？

2. 如果草药数量非常大，如何优化？

3. 如何将这个问题转化为其他类似的完全背包问题？

七、常见问题解答

‌Q: 为什么这里要正序遍历时间？‌
A: 正序遍历允许同一物品被多次选择，符合完全背包问题的要求。

‌Q: 如果时间或草药数量很大怎么办？‌
A: 可以考虑使用滚动数组进一步优化空间，或者寻找问题的特殊性质进行剪枝。

‌Q: 如何区分完全背包和01背包？‌
A: 关键区别在于物品是否可以重复选择，反映在代码上是遍历顺序的不同。