很好的思考题
可以注意到这题的权重是很小的W<=3，那么说明每一个物品加进来只会影响到附近最多三个.所以可以用贪心+dp来做。
#include <bits/stdc++.h> typedef long long ll; using namespace std; const int maxn = 1e5+7; const int inf=0x3f3f3f3f; struct node{ int w,c; double div; bool operator<(node b)const{ return div>b.div; } }a[maxn]; ll dp[300005]; int main(){ int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d%d",&a[i].w,&a[i].c),a[i].div=(double)a[i].c/(double)a[i].w; sort(a+1,a+1+n); memset(dp,-inf,sizeof(dp)); dp[0]=0; ll ans=0; int md=0; for(int i=1;i<=n;i++){ md+=a[i].w; if(md>m)md=m; int mdzz = max(a[i].w,md-6); for(int j=md;j>=mdzz;j--){ dp[j] = max(dp[j],dp[j-a[i].w]+a[i].c); ans=max(ans,dp[j]); } } printf("%I64d\n",ans); return 0; }