题解 | #草药大师#

草药大师

链接：https://ac.nowcoder.com/acm/problem/235951 来源：牛客网

做法1

因为最大容量有1e9，我们需要剪掉一些情况，对于每次物品我们只能拿一次，那么，其实也是从尾开始跑，只不过我们把从最大容量改成最大能放进的容量，如果总容量减去这一个物品的容量比原先的塞进去的容量大，说明可以拿当前这一个物品，那么就去把这一个物品塞进背包就行。

//本题代码
#include<bits/stdc++.h>
#define endl "\n"
#define int long long
//dont forget to check long long
//别写重变量名
//记得判越界
//别死磕
//处理字符串删掉关流
std::map<int, int> f;
void slove()
{
    int n,s;
    std::cin>>n>>s;
    std::vector<std::pair<int,int>> a(n+1);
    f[0]=0;
    int sum=0;
    for(int i=1;i<=n;i++) 
    {
        int x,y;
        std::cin>>x>>y;
        a[i]={x,y};
        sum+=x;
    }
    int ans=0;
    std::map<int,int>::reverse_iterator it;
    for(int i=1;i<=n;i++)
    {
        for(it=f.rbegin();it!=f.rend();it++)
        {
            if(s-a[i].first>=(*it).first)
            {
                f[(*it).first+a[i].first]=std::max( f[(*it).first+a[i].first], f[(*it).first]+a[i].second);
            }
        }
    }
   for(auto &i:f)
   {
       ans=std::max(ans,i.second);
   }
    std::cout<<ans<<endl;
    

}
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int T=1; 
    //std::cin>>T;
    while(T--)    {
        slove();
    }

    return 0;
}

做法2

启发式搜索，单纯的搜索就是在每个物品选与不选做决定，但有些情况是不必要的可以省去，我们只保留那些必要情况，那么什么是必要情况呢，首先考虑拿的话，只要当前的剩余容量还能塞，就塞进去，这是必然的。那不拿这么考虑呢？如果当前这个物品不拿，后面的所有物品尽可能都拿比现在要优，就可以选择不拿，要不然就是必须拿，这样就能减去大多数情况而不影响结果。

//本题代码
#include<bits/stdc++.h>
#define endl "\n"
#define int long long
//dont forget to check long long
//别写重变量名
//记得判越界
//别死磕
//处理字符串删掉关流
struct node{
    int num,t;
    double vaule;
    bool operator <(const node&t){
        return vaule>t.vaule;
    }
}a[510];
int n,m;
int ans=-1;
int f(int dep,int last)
{
    int sum=0;
    for(int i=1;i+dep<=n;i++)
    {
        if(a[i+dep].t<=last) 
        {
            sum+=a[i+dep].num;
            last-=a[i+dep].t;
        }
        else return (int)(sum+a[i+dep].vaule*last);
    }
    return sum;
}
void dfs(int dep,int cur,int last)
{
    ans=std::max(ans,cur);
    if(dep>n) return ;
    if(f(dep,last)+cur>ans) dfs(dep+1,cur,last);
    if(a[dep].t<=last)
    {
        dfs(dep+1,cur+a[dep].num,last-a[dep].t);
    }

}
void slove()
{
   std::cin>>n>>m;
   for(int i=1;i<=n;i++)
   {
        int x,y;
        std::cin>>x>>y;
        a[i]={y,x};
        a[i].vaule=1.0*y/x*1.0;
   }
   std::sort(a+1,a+1+n);
   dfs(1,0,m);
   std::cout<<ans<<endl;

}
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int T=1; 
    //std::cin>>T;
    while(T--)    {
        slove();
    }

    return 0;
}