经典与多人背包问题

经典背包问题中，我们所关心的问题在于“拿与不拿”，拿了就付出代价，获得收益，我们用f[ i ][ j ]表示第i个物体，在j限度内所能获得的最大收益，动规方程：

f[i][j]=max(f[i-1][j],f[i-1][j-cst[i]]+val[i]),j>=cst[i]

其描述内容是对于第i个物品的最大收益，取决于拿不拿他，如果不拿，收益与上一个物品的状态相同，反之如果拿了，此时收益就是付出代价后累加一个i物品的收益值

我们发现，上述动规方程的依赖关系是一个点依赖其上方和左上方的点，这样我们可以将数组压缩成两行，用取模操作控制当前行和上一行

f[i\%2][j]=max\{f[(i+1)\%2][j],f[(i+1)\%2][j-cst[i]]+val[i]\},j>=cst[i]

我们还可以继续考虑，如果一个点只是依赖上方的点（原始状态）和左上方的点（左边点的原始状态），我们不妨只用一个一维数组来储存信息，这样在进行每一轮操作时，每个点都是$f[i-1][j]$的状态，为了保证依赖关系成立，我们从这个数组的右边向左操作

这是终极版： f[j]=max(f[j],f[j-cst[i]]),j>=cst[i]

代码是这个样子的：

int f[maxV],cst[maxn],val[maxn],V,n;
int main(){
    sf("%d%d",&V,&n);
        for(int i=1;i<=n;i++)
        sf("%d%d",&cst[i],&val[i]);

    memset(f,0,sizeof(f));
    for(int i=1;i<=n;i++)
        for(int j=V;j>=cst[i];j--)
            f[j]=max(f[j],f[j-cst[i]]+val[i]);

    pf("%d",f[V]);
    return 0;
}

这便是经典背包问题了，而好消息是这种问题基本上不肯考到，出题的牲口们至少也会出形如P1858这类升级版问题

题目大意：在经典背包问题中，规定背包必须装满，求前k优解之和

我们不可能再用一维数组来解决这个问题了，不过借用其思路：原来f[ j ]表示空间为j时的最大收益，我们增加一维，用f[ j ][ k ]来表示空间为j时的第k大收益，那么f[ j ][ k ]所依赖的子问题将会是集合{f[ j ][]}与集合{f[ j-cst[ i ] ][]}了，因为该位置每一个解都有可能更新你的每一个解，上代码：

int f[maxV][maxk],cst[maxn],val[maxn],k,V,n;
int main(){
    sf("%d%d%d",&k,&V,&n);
    for(int i=1;i<=n;i++)
        sf("%d%d",&cst[i],&val[i]);
    //f[i][j]表示i体积下第j优解（收益

    memset(f,0x83,sizeof(f));
    f[0][1]=0;//必须装满的初始化

    int a[maxn];//临时存放数据用的
    for(int i=1;i<=n;i++)
        for(int j=V;j>=cst[i];j--){//前面完全一致
            int p=1,q=1;//p不买，q买
            for(int l=1;l<=k;l++)//用l去列举每一个解
                if(f[j][p]>f[j-cst[i]][q]+val[i])
                    a[l]=f[j][p++];
                else
                    a[l]=f[j-cst[i]][q++]+val[i];
            for(int l=1;l<=k;l++)
                f[j][l]=a[l];//这里是答案
        }

    int ans=0;
    for(int i=1;i<=k;i++)
        ans+=f[V][i];
    pf("%d",ans);

    return 0;
}