洛谷 P1858 多人背包『第k优背包』 题解【DP】【背包】【归并】

作者: wjyyy 分类: DP,归并,背包,解题报告 发布时间: 2018-07-13 16:40

点击量:26

 

   DP套归并!

 

题目描述

求01背包前k优解的价值和,且背包必须装满。

输入输出格式

输入格式:

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

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

输出格式:

前\(k\)优解的价值和

输入输出样例

输入样例#1:
2 10 5
3 12
7 20
2 4
5 6
1 1
输出样例#1:
57

说明

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

题解:

   因为第\(k\)优解与第\(k+1\)优解没有严格与某个物品的选或不选有关系,因此不能用分层图转移的思想来做。不过因为最优解到第k优解的答案总是(非严格)递增的,所以考虑排序取最优,那么对哪些数据排序呢?

   对于这个题的状态,设为f[i][j],表示已经装\(i\)空间的物品的第\(j\)优解(压掉了第一维)。对于一般的背包,状态转移方程为

f[i][j]=第j大(f[i][k1],f[i-c][k2]);

   其中\(k1-1+k2-1=j-1\),因为前\(k1-1\)个数和前\(k2-1\)个数凑成了\(f[i]\)的前\(j-i\)优解,就是归并的思想。假设第一个队列为\(f[i][]\),第二个队列为\(f[i-c][]+v\),我们每次取最优的那个,当\(f[i][1]\)弹出后,就用\(f[i][2]\)和\(f[i-c][1]\)比,类似归并把答案存在另一个数组中(防止冲突),最后再\(\tt copy\)回\(f[i]\)的前\(k\)优解。

我们有两个单增序列,要求它们的前k大值

可以用归并的思路,用两个头指针判断哪个更大,就把哪个放到临时队列里。

最后把临时队列再赋值给\(f[i][1…k]\)就可以了。

 

   非常正常容易想到的简单的归并思路题///。

 

Code:

#include<cstdio>
#include<cstring>
int max(int x,int y)
{
    return x>y?x:y;
}
int f[5010][55];
int tmp[55];
int main()
{
    memset(f,-0x3f,sizeof(f));
    f[0][1]=0;
    int k,n,v,c,w;
    scanf("%d%d%d",&k,&v,&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&c,&w);
        for(int j=v;j>=c;j--)
        {
            int t1=1,t2=1;//归并用
            for(int l=1;l<=k;l++)
                if(f[j][t1]<f[j-c][t2]+w)
                    tmp[l]=f[j-c][t2++]+w;
                else
                    tmp[l]=f[j][t1++];
            for(int l=1;l<=k;l++)
                f[j][l]=tmp[l];
        }
    }
    int ans=0;
    for(int i=1;i<=k;i++)
        ans+=f[v][i];
    printf("%d\n",ans);
    return 0;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */