先上题目链接:

然后放AC代码:

#include
      
       #define ll long longusing namespace std;ll f[100010];ll timee[10010];ll w[10010];int main(){    ll t,m;    cin>>t>>m;//t总时间,m总草药    //time时间,w价值    for(ll i=1;i<=m;i++)    {        scanf("%lld",&timee[i]);        scanf("%lld",&w[i]);    }    for(ll i=1;i<=m;i++)        for(ll j=timee[i];j<=t;j++)        {            f[j]=max(f[j],f[j-timee[i]]+w[i]);        }    cout<
       
        <
       
      

然后推荐一道类似的题目:

不同点在与这题是完全背包,采药那题是01背包,

还有就是疯狂的采药数据比较大,建议用滚动数组,如果用二维数组不知道会不会不行,我没试过.

然后讲一下思路:

假定你已经学过滚动数组和01背包了,那么这题就很简单了,相对于普通的01背包来说,如果用滚动数组的话,

对于for的第二维也就是代表剩余空间那一维是从大到小遍历的,这样就能防止每个物品放了超过一次以上,

也就是新数据覆盖旧数据后在这次循环中新数据不会被再覆盖,放在实际层面就是一个物品只能被放一次

 

如果现在把for的第二维也就是代表剩余空间那一维是从小到大遍历,那么新数据也可能被覆盖,也就是一个物品放了后还可能接着放,

这样一来就从01背包转移到完全背包了

 

至于能用滚动数组的原因是第i层只和第i-1层有关