Herbs Gathering有一个容量为 \(m\) 的背包，有 \(n\) 种草药，每种草药都有只有一株，每株草药都有价值 \(v\) 和体积 \(w\),问能得到的草药价值最高为多少。
\(1\leq m\leq10^9,1\leq n\leq10^2\)
考虑到 \(n\) 的数据范围较小所以我们使用搜索，对于每株草药我们枚举它选还是不选
最后统计最大价值
剪枝:
按照体积从大到小排序
① 维护体积和价值的前缀和，如果当前剩余未考虑草药能取完，那就直接取完并且 \(return\)
② 如果，当前已经得到的价值 \(+\) 剩余未考虑草药的价值和 \(\leq\) 当前答案，就 \(return\)
体积从大到小排序，是为了更加高效地剪枝（不这样排序就会 TLE）
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
const int maxn=110;
int n,m;
struct bags
{
int v,w;
}bag[maxn];
bool cmp(const bags &a,const bags &b)
{
return a.w>b.w;
}
long long ans=0,sumw[maxn],sumv[maxn];
void dfs(int pos,long long sum,long long val)
{
if(pos==n)
{
if(bag[pos].w<=sum)ans=max(val+bag[pos].v,ans);
else ans=max(ans,val);
return;
}
if(val+sumv[pos]<=ans)return;
if(sumw[pos]<=sum)
{
ans=max(ans,val+sumv[pos]);
return;
}
dfs(pos+1,sum,val);
if(bag[pos].w<=sum)dfs(pos+1,sum-bag[pos].w,val+bag[pos].v);
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
ans=0;
sumw[n+1]=0;
sumv[n+1]=0;
for(int i=1;i<=n;i++)scanf("%d%d",&bag[i].w,&bag[i].v);
sort(bag+1,bag+1+n,cmp);
for(int i=n;i>=1;i--)
{
sumw[i]=bag[i].w+sumw[i+1];
sumv[i]=bag[i].v+sumv[i+1];
}
dfs(1,m,0);
printf("%lld\n",ans);
}
}原文：https://www.cnblogs.com/Harry-bh/p/8830459.html