ABCD

源代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int m,n,Num(0),Ans(0),A[201],B[201],C[201],D[201],i[3001],j[3001],f[100001];
void Solve(int S,int V,int W) //二进制优化。
{
    for (int a=1;a<=S;a*=2)
    {
        j[++Num]=V*a;
        i[Num]=W*a;
        S-=a;
    }
    if (S)
    {
        j[++Num]=S*V;
        i[Num]=S*W;
    }
}
int main() //多重背包。
{
    memset(f,-0x3f,sizeof(f)); //赋极小值。
    f[0]=0;
    scanf("%d",&n);
    for (int a=1;a<=n;a++)
    {
        scanf("%d%d%d%d",&A[a],&B[a],&C[a],&D[a]);
        B[a]-=A[a];
        Ans+=A[a]*D[a]; //真应得的价值。
        m-=A[a]*C[a]; //真应减少的体积。
    }
    for (int a=1;a<=n;a++)
      Solve(B[a],C[a],D[a]);
    for (int a=1;a<=Num;a++)
      for (int b=m;b>=j[a];b--)
        f[b]=max(f[b],f[b-j[a]]+i[a]);
    printf("%d",f[m]+Ans);
    return 0;
}

/*
    又是有关于变式的一道题。
    可以将问题看做一个多重背包，可选个数为0~B[a]-A[a]，体积为C[a]，价值为D[a]。
    背包的体积为∑(-A[a]*C[a])，所以一开始便有了初始总价值∑(A[a]*D[a])。
    看清楚范围！不必担心体积越界的问题。
*/