Luogu p1858 [multi person knapsack] (knapsack seeking the top k optimal solution)

Title Description ：

a key ： seek  01  In front of the backpack  k  The value of optimal solution and , And the backpack should be full .

Algorithm analysis ：

First ,01  Backpacks should be familiar to everyone , We won't talk about transfer here .

Let's start with the first part ： How to keep your backpack full ？

natural  01  The knapsack is from the array with an initial value of  0  Start , That is, every volume will transfer , It is possible to update the answer .

But if you want to fill it up , obviously , Insufficient volume ( No  n  The volume and energy of an object is this volume ) Obviously not . It seems difficult , But never mind. , We put  f  The array is first assigned to the minimum value .

What's the advantage of this ？ Will find , Because it's painting down layer by layer , So the first layer obviously has only the volume, which is exactly the volume of the first article , The maximum value will be updated ( Because everything else is negative infinity , Will not update ).

Then start painting the second layer , obviously , Only the volume brushed on the first layer , Will then move back ( Because everything else is transferred from negative infinity , It makes no sense , It can't be the maximum ).

Then pay attention to  ff  The array should have an initial value of  0 ( Later on ).

Let's look at the second part ： Seek before  k  The value of optimal solution and .

set up  f[i][j]  The volume is  i, The first  j  The value of the optimal solution . At this time , Above said  f  The initial value of the array can be assigned . hold  f[0][1]  The assignment is  0, Because the volume is  0  The optimal solution is obviously  0.

We need to consider before  k  Excellent solution . Start with the optimal solution and look back .

01  Backpack is  f[j]  and f[j−w[i]]+v[i]  The transfer of , Then this question can learn from this idea .

set up  x,y  The optimal solutions on both sides . If f[j][x]>f[j−w[i]][y], We use an array rnk  Before deposit  k  Excellent solution , At this time rnk[++cnt]=f[j][x], And the x+1. On the contrary, the same is true .

What does this passage mean ？ Is to record the capacity of these two backpacks , Which one is big .

Finally, put... Outside  f  The array has a volume of  j  Under the condition of  k  The optimal solution is assigned as rnk  An array of former  k  Just one .

Master code ：

#include<bits/stdc++.h>
#define re register
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch == '-') f=-1 ; ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48) ; ch=getchar();}
    return x*f;
}
inline void print(int x){
    if(x/10) print(x/10);
    putchar(x%10+'0');
}
const int M = 5010;
int k,value,n,ans;
int w[M],v[M],f[M][60],rnk[M];
signed main(){
    k=read(),value=read(),n=read();
    for(re int i(1) ; i<=n ; ++i) scanf("%d%d",&w[i],&v[i]);
    memset(f,-0x7f7f7f7f,sizeof(f));
    f[0][1] = 0;
    for(re int i(1) ; i<=n ; ++i){
        for(re int j(value) ; j>=w[i] ; --j){
            int rn1=1,rn2=1,cnt=0;
            while(cnt<=k){
                if(f[j][rn1] > f[j-w[i]][rn2]+v[i]){
                    rnk[++cnt] = f[j][rn1];
                    rn1++;
                }
                else{
                    rnk[++cnt] = f[j-w[i]][rn2]+v[i];
                    rn2++;
                }
            }
            for(re int h(1) ; h<=k ; ++h) f[j][h] = rnk[h];
        }
    }
    for(re int i(1) ; i<=k ; ++i) ans += f[value][i];
    printf("%d",ans);
    return 0;
}