把每体积的干草价值看成一，就变成求最大价值
直接上背包就行了
注意优化常数
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=1e5+7; int n,m; int a[N],f[N]; int main() { m=read(); n=read(); for(int i=1;i<=n;i++) a[i]=read(); for(int i=1;i<=n;i++) { for(int j=m;j>=0;j--) if(j+a[i]<=m) f[j]=max(f[j],f[j+a[i]]+a[i]); if(f[0]==m) break;//剪枝 } int ans=0; for(int i=0;i<=n;i++) ans=max(ans,f[i]); printf("%d",ans); return 0; }