如果没有 b [ i ] 就是01背包
加上 b [ i ] 这个属性，我们可以考虑：对于1,2两个，
先完成1的价值p=a[1]-b[1]*c[1]+a[2]-b[2]*(c[1]+c[2])
先完成2的价值q=a[2]-b[2]*c[2]+a[1]-b[1]*(c[1]+c[2])
p>q 要求 b[1]c[2]>b[2]c[1]
故满足这个条件上的所有物品对（x,y）只需满足 b[x]c[y]>b[y]c[x]即先选x更优
按序号在前面的更优排序后背包即可
f [ j ] 表示 j 时刻所能得到的最大价值（0<=j<=100,000）
f [ j + e [ i ] . c ] = max ( f [ j + e [ i ] . c ] , f [ j ] + e [ i ] . a - ( j + e [ i ] . c ) * e [ i ] . b ) ;
注意开long long
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 #define ll long long 6 const int N=100010; 7 ll f[N],ans; 8 struct fx{ 9 ll a,b,c; 10 }e[N]; 11 bool cmp(fx x,fx y){ 12 return x.b*y.c>y.b*x.c; 13 } 14 ll max(ll x,ll y){ 15 return x>y?x:y; 16 } 17 int main(){ 18 int n,t; 19 scanf("%d %d",&t,&n); 20 for (int i=1;i<=n;i++) 21 scanf("%lld",&e[i].a); 22 for (int i=1;i<=n;i++) 23 scanf("%lld",&e[i].b); 24 for (int i=1;i<=n;i++) 25 scanf("%lld",&e[i].c); 26 memset(f,0,sizeof(f)); 27 sort(e+1,e+n+1,cmp); 28 for (int i=1;i<=n;i++) 29 for (int j=t-e[i].c;j>=0;j--) 30 f[j+e[i].c]=max(f[j+e[i].c],f[j]+e[i].a-(j+e[i].c)*e[i].b); 31 ans=0; 32 for (int j=0;j<=t;j++) 33 ans=max(ans,f[j]); 34 printf("%lld",ans); 35 return 0; 36 }