背包问题第K优解

首先，我们由一道题引入：小L打怪兽

很明显，对于这道题，$k=1$时我们要求的就是一个完全背包问题，但$1\le k\le100$，这时我们可以考虑多开一位状态，用$dp[i][j]$表示花费$i$体力情况下第$j$优解，我们知道在完全背包中$dp[i]=max(dp[i],dp[j-v]+w)$，这时我们就可以用类似归并排序的思想来转移状态，看代码应该就懂了。

#include<bits/stdc++.h>
#define x first
#define y second
#define endl '\n'
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define lowbit(x) ((x)&-(x))
#define SZ(x) (int)x.size()
using namespace std;
using ll=long long;
using ld=long double;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using pdd=pair<ld,ld>;
const int INF=0x3f3f3f3f;
const int N=3e3+10,K=110;
int dp[N][K];
int tmp[K];
int n,m,k,w,v;
void solve(){
	cin>>k>>m>>n;
    for(int i=0;i<=m;i++)
        for(int j=0;j<=k;j++)
            dp[i][j]=-INF;
    dp[0][1]=0;
    for(int i=1;i<=n;i++){
        cin>>v>>w;
        for(int j=v;j<=m;j++){
            int str1=1,str2=1,len=0;
            while(str1+str2<=k+1){
                if(dp[j][str1]>dp[j-v][str2]+w) tmp[++len]=dp[j][str1++];
                else tmp[++len]=dp[j-v][str2++]+w;
            }
            for(int x=1;x<=k;x++)
                dp[j][x]=tmp[x];
        }
    }
    cout<<(dp[m][k]<0?-1:dp[m][k])<<endl;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
    int T;
    cin>>T;
    while(T--)
	solve();
	return 0;
}