题解 P1616 【疯狂的采药】

⚡小林子⚡ · 2020-08-30 13:43:59 · 题解

一道考察完全背包的题目。

题目传送门

upd：添加了对完全背包状态转移方程式的详细推导过程。

正文

设 f_{i,j} 表示前 i 件物品采药 j 时间能获得的最大价值。

可以列出状态转移方程：

f_{i,j}=\max\limits_{k=0}^{k\le \frac{j}{w_i}} (f_{i-1,j-k\times w_i}+k\times v_i)

使用二维 dp 显然超时超空间，考虑优化 dp。

把第 i 种草药拆成体积为 w_i\times 2 价值 v_i\times 2 的物品，其中满足 w_i\times 2\le j。

对于第 i 种草药的出现，我们对第 i 种草药要不要采进行决策。如果不放那么 f_{i,j}=f_{i-1,j}；
如果确定采，那么应该出现至少一个第 i 种草药，所以当前至少应该出现一个第 i 种草药,即 f_{i,j}=f_{i,j-w_i}+v_i。

那么完全背包和 01 背包的不同点在哪里呢？

从二维数组上区别 01 背包和完全背包也就是状态转移方程就差别在采第 i 种草药时，完全背包在选择采这个草药时，最优解是 f_{i,j-w_i}+v_i 即同行的那一个，而 01 背包比较的是f_{i-1,j-w_i}+v_i，上一行的那一个。

时间优化完成了，但是此时空间还是会超，考虑滚动数组。

是否能滚动数组呢？答案当然是可以的。

假设只有一惟 f_i，如果是倒序推那么当前 f_1 ~ f_{i-1} 都是上一个草药遗留下来的状态，显然不符合要求。

正序推的话 f_1 ~ f_{i-1} 均为当前草药已经推过的状态，符合要求。

所以完全背包和 01 背包的区别就在于对时间大小枚举的顺序不同。

具体代码也就好写了：

for(int i=1;i<=n;i++)
    for(int j=w[i];j<=m;j++)
        f[j]=max(f[j],f[j-w[i]]+v[i]);

以上为核心代码。

接下来要注意本题数据范围（有一个坑点）

本题最多有 10^7 时间，每种草药的价值最大是 10^4，所以极限情况下价值总和是 10^7\times 10^4=10^{11}，会爆 int，所以要开 long long。

十年 OI 一场空，不开 long long 见祖宗。

Code：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e4+5,M=1e7+5;
int n,m,w[N],v[N],f[M];
signed main(){
    scanf("%lld%lld",&m,&n);
    for(int i=1;i<=n;i++)
        scanf("%lld%lld",&w[i],&v[i]);
    for(int i=1;i<=n;i++)
        for(int j=w[i];j<=m;j++)
            f[j]=max(f[j],f[j-w[i]]+v[i]);
    printf("%lld",f[m]);
    return 0;
}

AC！

总结

noip 临近，在此提醒大家做题一定要看数据范围，防止因为没开 long long 而遗憾失分。

建议使用 scanf 和 printf，虽然要打的字符多一些，但是时间更快（或者您使用 ios::sync_with_stdio(0) 也可以），防止考场上因为输入输出而 TLE。

题解 P1616 【疯狂的采药】

正文

总结

\sf{The\,End.}