题面

题目链接

洛谷 P1858 多人背包

题目描述

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

输入输出格式

输入格式

第一行三个数 $ K,V,N $

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

输出格式

前 $ k $ 优解的价值和

输入输出样例

输入样例

输出样例

说明

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

【时空限制】

1000ms,128MB

思路

求k优解。可以考虑开二维数组f[v][k]，表示装v体积物品的第k优解

加入每一件物品时，就要更新f[V]到f[v[i]]的值。对于新的f[v]，应该是当前的f[v]与f[v-v[i]]+w[i]合并后的序列，取其中前k优就好了

AC代码

#include<bits/stdc++.h>

const int maxk=60;

const int maxn=210;

const int maxv=5010;

using namespace std;

int k,V,n;

int v[maxn],w[maxn];

int f[maxv][maxk];

int ans;

int main()

{

    scanf("%d%d%d",&k,&V,&n);

    for(int i=1;i<=n;i++) scanf("%d%d",&v[i],&w[i]);

    for(int i=0;i<=V;i++)

        for(int j=0;j<=k;j++)

        f[i][j]=-100000;

    f[0][1]=0;

    for(int i=1;i<=n;i++)

    {

        for(int j=V;j>=v[i];j--)

        {

            int p1=1,p2=1,tmp[maxk];

            while(p1+p2-1<=k)

            {

                if(f[j][p1]>f[j-v[i]][p2]+w[i]) tmp[p1+p2-1]=f[j][p1],p1++;

                else tmp[p1+p2-1]=f[j-v[i]][p2]+w[i],p2++;

            }

            for(int t=1;t<=k;t++) f[j][t]=tmp[t];

        }

    }

    for(int t=1;t<=k;t++) ans+=f[V][t];

    printf("%d",ans);

    return 0;

}

秒客网

洛谷 P1858 多人背包 DP

题面