题意

题目描述

求\(01\)背包前\(k\)优解的价值和

输入输出格式

输入格式：

第一行三个数\(K\)、\(V\)、\(N\)

接下来每行两个数，表示体积和价值

输出格式：

前\(k\)优解的价值和

输入输出样例

输入样例#1：

输出样例#1：

说明

对于\(100\%\)的数据,\(K\leq 50,V\leq 5000,N\leq 200\)

思路

让我先秒了这道水题。 --Mercury

多重背包。考场上考到的时候使用的是\(STL\)中的优先队列求解，即对于每一个\(V\)状态开一个优先队列，更新时逐个取出再插入，超过\(50\)个时后面的不用再插回去了。

这是一种显然的~~蚊子打高射炮~~高射炮打蚊子的做法，我们不妨这么想：

对于一般的\(01\)背包问题，我们有标准的状态转移方程\(f[i]=max(f[i],f[i-v[j]]+w[j])(i\geq v[j])\)。也就是说，对于每个物品而言，状态\(f[i]\)只与\(f[i]\)和\(f[i-v[j]]\)有关，所以我们不妨设计\(f[i][j]\)表示\(f[i]\)的第\(j\)优解，更新时因为\(f[i][j]\)是有单调性的，所以拿单调指针从左往右扫一遍，扫出\(k\)个最优解，来更新就好了：

for(int i=V;i>=v[j];i--)//01背包倒序枚举
{
    int cnt=0,cfr=0,cto=0;//cnt记录更新后的解，cto记录更新前的解，cfr记录f[i-v[j]]的解
    while(cnt<k)//找到k个解
        if(f[i][cto]>f[i-v[j]][cfr]+w[j]) tmp[cnt++]=f[i][cto++];//扫描
        else tmp[cnt++]=f[i-v[j]][cfr++]+w[j];
    for(int w=0;w<k;w++) f[i][w]=tmp[w];//更新
}

AC代码

#include<bits/stdc++.h>
using namespace std;
int k,v,n,ans,f[5005][55],tmp[55];
int read()
{
    int re=0;char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) re=(re<<3)+(re<<1)+ch-'0',ch=getchar();
    return re;
}
int main()
{
    k=read(),v=read(),n=read();
    memset(f,0xcf,sizeof f);
    f[0][0]=0;
    while(n--)
    {
        int x=read(),y=read();
        for(int i=v;i>=x;i--)
        {
            int cnt=0,cfr=0,cto=0;
            while(cnt<k)
                if(f[i][cto]>f[i-x][cfr]+y) tmp[cnt++]=f[i][cto++];
                else tmp[cnt++]=f[i-x][cfr++]+y;
            for(int j=0;j<k;j++) f[i][j]=tmp[j];
        }
    }
    for(int i=0;i<k;i++) ans+=f[v][i];
    printf("%d",ans);
    return 0;
}

Luogu P1858 多人背包

题意