首页 > 其他 > 详细

多人01背包(背包k优解)

时间:2019-01-24 20:33:16      阅读:295      评论:0      收藏:0      [点我收藏+]

洛谷P1858 多人背包

K个包的容量都是V.可以装进背包里的一共有N种物品,每种物品都有给定的体积和价值。

合理的背包安排方案是这样的:

1 每个背包里装的物品的总体积恰等于包的容量。

2 每个包里的每种物品最多只有一件,但两个不同的包中可以存在相同的物品。

3 任意两个包里的物品清单不能完全相同。

在满足以上要求的前提下,所有包里的所有物品的总价值最大是多少呢?即求01背包前k优解的价值和.

首先我们就只考虑最普通的01背包问题.

\(f[i][j]\)表示前i件物品,放入容量为j的背包中,可以获得的最大价值.\(w[i]\)表示第i件物品的体积,\(val[i]\)表示第i件物品的价值.则有:

f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+val[i])

使用滚动数组,优化空间复杂度 ,则有:

f[j]=max(f[j],f[j-w[i]]+val[i]);

我们发现\(f[j]\)只可能由\(f[j]\)或者\(f[j-w[i]]+val[i]\)推来,且一定等于两者中的较大者.

现在我们要求前k个最优解,则在滚动数组的基础上增加一维k,设\(f[i][k]\)表示体积为i时的第k优解的值.

显然,\(f[i][1]...f[i][k]\)是一个单调递减的序列.

因为在普通01背包中,我们只在乎的是最优解(在此处就相当于\(f[i][1]\)),不在乎它怎么比较出最优解的这个过程.而本题中求k优解,要求我们在乎这些过程,都需要记录.

换句话说,我们需要记录的是不断用等价(体积)的物品去填充一个背包,从而不断地得到不同的总价值,然后从这些不同的总价值中比较得出最优解,次优解...k优解.

再通过上面的分析:"我们发现\(f[j]\)只可能由\(f[j]\)或者\(f[j-w[i]]+val[i]\)推来." 可知:

我们需要两个变量\(l1\)\(l2\),分别表示体积为\(j\)\(j-w[i]\)时两种情况下的第\(l1\)\(l2\)优解.

此时我们会有两个队列,一个队列是\(l1\)表示的体积为\(j\)的时候的解,还有一个队列是\(l2\)表示的体积为\(j-w[i]\)的时候的解,因为两个队列都是单调递减的,由上文中"且一定等于两者中的较大者"可得,我们只需要每一次取出两个队头比较大小,\(f[j][]\)就等于两者之中较大者,比较k次之后,\(f[j][1..k]\)就全都求出来了.这实际上利用的是归并排序的思想.


int k,v,n,ans;
int f[5001][51],w[201],val[201],now[51];
int main(){
    k=read();v=read();n=read();
//k优解,v每个背包的最大容量,n物品种数
    for(int i=1;i<=n;i++){
        w[i]=read();
        val[i]=read();
    }
//读入每个物品的体积w以及价值val.
//其实本题可以直接一边读入物品信息一边处理.但没必要
    for(int i=0;i<=v;i++)
    for(int j=1;j<=k;j++)
        f[i][j]=-2147483647;
    f[0][1]=0;
//f[0][1]表示背包体积为0时的最优解
//因为"任意两个包里的物品清单不能完全相同"
//所以f[0][2...k]都只能是负无穷
//这里将其它值都赋为负无穷,还可以根据它们的正负
//来判断它们是否访问(处理)过.
//有一个地方解释,在动态规划中把不合法的情况设为负无穷
//你要这样理解也可以,反正你自己明白就行
    for(int i=1;i<=n;i++)
    for(int j=v;j>=w[i];j--){
        if(f[j-w[i]][1]>=0){
//体积为j-w[i]时的最优解不为负值,表示其有意义
//或者说这种情况之前已经更新过,是合法的.
//下面开始归并排序:
            int l1=1,l2=1,cnt=0;
            while(cnt<=k){
                if(f[j][l1]>f[j-w[i]][l2]+val[i])
                    now[++cnt]=f[j][l1++];
                else now[++cnt]=f[j-w[i]][l2++]+val[i];
            }
            for(int kk=1;kk<=k;kk++)
                f[j][kk]=now[kk];
//now数组只是归并过程中记录每一次比较结果的数组
//最后都要赋给f数组
        }
    }
    for(int i=1;i<=k;i++)
        ans+=f[v][i];
    printf("%d\n",ans);
//把前k优解的值都累加起来输出
    return 0;
}

多人01背包(背包k优解)

原文:https://www.cnblogs.com/PPXppx/p/10316592.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!