洛谷 P1858 多人背包 解题报告

时间：2021-02-15 07:28:32

P1858 多人背包

题目描述

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

输入输出格式

输入格式：

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

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

输出格式：

前k优解的价值和

说明

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

算是积累见识吧，有些类型的题不见过一面估计比较难想

方程为\(dp[i][j][k]\)代表前\(i\)中在装了\(j\)时第\(k\)优值

如何转移呢

对\(dp[i][j]\)来说，由\(dp[i-1][j]\)和\(dp[i-1][j-w]+c\)转移

即我们从\(dp[i-1][j][1...k]\)和\(dp[i-1][j-w][1...k]+c\)中选出前\(k\)大的给\(dp[i][j][1...k]\)

用到了归并排序的思想

Code:

#include <cstdio>

#include <cstring>

int max(int x,int y){return x>y?x:y;}

int min(int x,int y){return x<y?x:y;}

const int inf=0x3f3f3f3f;

int k,v,n,dp[52][5010],c,w,tmp[52];

int main()

{

    memset(dp,-0x3f,sizeof(dp));

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

    dp[1][0]=0;

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

    {

        scanf("%d%d",&w,&c);

        for(int j=v;j>=w;j--)

        {

            int l1=1,l2=1,cnt=0;

            while(l1+l2<=k+1)

            {

                if(dp[l1][j]>dp[l2][j-w]+c)

                    tmp[++cnt]=dp[l1++][j];

                else

                    tmp[++cnt]=dp[l2++][j-w]+c;

            }

            for(int l=1;l<=k;l++) dp[l][j]=tmp[l];

        }

    }

    int ans=0;

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

        ans+=dp[i][v];

    printf("%d\n",ans);

    return 0;

}

2018.7.13

相关文章