题解 P1616 【疯狂的采药】

· · 题解

本题解主要详细讲述了完全背包算法的原理

这题是一个标准的完全背包问题，在分析的时候我们就把题目中的背景去掉，体积就是时间，这样更有利于分析此题以及联想其他背包题目

不难得出递推式：dp_i = max(dp_i,dp_{i-v} + w)

————这里已经进行了数组压维，这样可以优化空间

我们先来假设一下输入数据是这样的：

4 5
1 2
2 4
3 4
4 5

不难看出输出应该是 10

但是究竟是怎样得出这个结果的呢?

下面展示一下原理：（ v_i 为体积，w_i 为价值）

首先dp数组初始化全为0：给定物品种类有4种，包最大体积为5，数据来源于题目的输入
v[1] = 1, w[1] = 2
v[2] = 2, w[2] = 4
v[3] = 3, w[3] = 4
v[4] = 4, w[4] = 5

i = 1 时： j从v[1]到5
dp[1] = max(dp[1],dp[0]+w[1]) = w[1] = 2 (用了一件物品1）
dp[2] = max(dp[2],dp[1]+w[1]) = w[1] + w[1] = 4（用了两件物品1）
dp[3] = max(dp[3],dp[2]+w[1]) = w[1] + w[1] + w[1] = 6（用了三件物品1）
dp[4] = max(dp[4],dp[3]+w[1]) = w[1] + w[1] + w[1] + w[1] = 8（用了四件物品1）
dp[5] = max(dp[3],dp[2]+w[1]) = w[1] + w[1] + w[1] + w[1] + w[1] = 10（用了五件物品）

i = 2 时：j从v[2]到5
dp[2] = max(dp[2],dp[0]+w[2]) = w[1] + w[1] = w[2] =  4（用了两件物品1或者一件物品2）
dp[3] = max(dp[3],dp[1]+w[2]) = 3 * w[1] = w[1] + w[2] =  6（用了三件物品1，或者一件物品1和一件物品2）
dp[4] = max(dp[4],dp[2]+w[2]) = 4 * w[1] = dp[2] + w[2] =  8（用了四件物品1或者，两件物品1和一件物品2或两件物品2）
dp[5] = max(dp[5],dp[3]+w[2]) = 5 * w[1] = dp[3] + w[2] =  10（用了五件物品1或者，三件物品1和一件物品2或一件物品1和两件物品2）

i = 3时：j从v[3]到5
dp[3] = max(dp[3],dp[0]+w[3]) = dp[3] = 6 # 保持第二轮的状态 
dp[4] = max(dp[4],dp[1]+w[3]) = dp[4] = 8 # 保持第二轮的状态 
dp[5] = max(dp[5],dp[2]+w[3]) = dp[4] = 10 # 保持第二轮的状态

i = 4时：j从v[4]到5
dp[4] = max(dp[4],dp[0]+w[4]) = dp[4] = 10 # 保持第三轮的状态
dp[5] = max(dp[5],dp[1]+w[4]) = dp[5] = 10 # 保持第三轮的状态

上面模拟了完全背包的全部过程，也可以看出，最后一轮的dp[m]即为最终的返回结果。

这便是完全背包的基本原理，应用到本题也是一样

那么这个算法的时间复杂度就是 O(nm) 不会出现 TLE 的情况

注意：本题数据已更新，需要开 longlong !

下面附上AC代码：

//这里代码中t数组就是上面讲解的v数组，v数组是上面的w数组
//因为我写代码的时候按背景中的时间(time)和价值(value) 写的
#include<iostream>
#include<algorithm>
using namespace std;
const int maxm = 10010, maxt = 10000010;
long long v[maxm], t[maxm], f[maxt];//开longlong！
int main(){
    int T , m;
    cin >> T >> m;
    for(int i = 1;i <= m ;i ++) cin >> t[i] >> v[i];
    for(int i = 1;i <= m;i ++){
        for(int j = t[i];j <= T;j ++){
            f[j] = max(f[j],f[j - t[i]] + v[i]);
        }
    }
    cout << f[T];
}

感觉讲的挺详细的，完结撒花！