洛谷 P1858 多人背包解题报告

P1858 多人背包

题目描述

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

输入输出格式

输入格式：

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

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

输出格式：

前k优解的价值和

说明

对于100%的数据,$ Kle 50,Vle 5000,Nle 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
",ans);
    return 0;
}

2018.7.13