题目描述
求01背包前k优解的价值和
输入输出格式
输入格式：
第一行三个数K、V、N
接下来每行两个数，表示体积和价值
输出格式：
前k优解的价值和
输入输出样例
输入样例#1：
2 10 5
3 12
7 20
2 4
5 6
1 1
输出样例#1：
57
说明
对于100%的数据,K≤50,V≤5000,N≤200
(Solution:)
求第k优解的背包问题当然还是用背包做啦！
由于要求前k优解，所以我们可以开一个 (f_{j,k}) 来表示容量为 (j) 的第 (k) 优解，递推的时候由于你记录的是 (k) 优解，那么最多产生 (2*k) 种情况，我们不妨可以再开一个 (now) 数组来记录这 (2*k) 种情况，然后使它有序并把前 (k) 个赋值给 (f_{j,k}) ，最后统计一下答案就好了qwq
上代码，代码中会有具体解释：
#include<bits/stdc++.h>
#define il inline
using namespace std;
il int read(){
int f=1,w=0;char c=0;
while(!isdigit(c))
{
if(c=='-') f=-1;
c=getchar();
}
while(isdigit(c)) w=w*10+(c^48),c=getchar();
return f*w;
}//快读不解释
int k,v,n,w[210],c[210],f[5010][55],now[5010],ans;
int main(){
k=read(),v=read(),n=read();
for(int i=1;i<=n;i++) c[i]=read(),w[i]=read();
memset(f,-0x3f,sizeof(f));
f[0][1]=0;//初始化
for(int i=1;i<=n;i++)
for(int j=v;j>=c[i];j--)
{
int c1=1,c2=1,m=0;
while(m<=k)
{
if(f[j][c1]>f[j-c[i]][c2]+w[i])
now[++m]=f[j][c1++];
else now[++m]=f[j-c[i]][c2++]+w[i];
}//在赋值过程中一并排完序，f[j]与f[j-c[i]]都是有序的
for(int o=1;o<=k;o++) f[j][o]=now[o];
}
for(int i=1;i<=k;i++) ans+=f[v][i];//计算答案
printf("%d",ans);
return 0;
}