文档章节

多重背包

曾劲松
 曾劲松
发布于 2016/08/04 22:21
字数 1234
阅读 21
收藏 0

http://blog.csdn.net/insistgogo/article/details/11176693

1、问题描述

    已知:有一个容量为V的背包和N件物品,第i件物品最多有Num[i]件,每件物品的重量是weight[i],收益是cost[i]。问题:在不超过背包容量的情况下,最多能获得多少价值或收益

A---直接扩展01背包的方程

时间复杂度:和基本思路一样,没有降低。

时间复杂度:程序需要求解N*V个状态,每一个状态需要的时间为O(v/Weight[i]),总的复杂度为O(NV*Σ(V/Weight[i]))。

/*
状态转移方程:  
f[i][v]:表示前i件物品放入重量为v的背包获得的最大收益  
f[i][v] = max(f[i][v], f[i-1][V-k* Weight[i]] + k * Value[i]);  
其中0 <= k <= min(Num[i],V/Weight[i]);//这里和完全背包不同。  
边界条件  
f[i][0] = 0;  
f[0][v] = 0;  
*/

#include <iostream>  
using namespace std;  
const int N = 3;//物品个数  
const int V = 8;//背包容量  
int Weight[N + 1] = {0,1,2,2};  
int Value[N + 1] = {0,6,10,20};  
int Num[N + 1] = {0,10,5,2};  
int f[N + 1][V + 1] = {0};  
 
int MultiKnapsack()  
{  
    int nCount = 0;  
    //初始化  
    for (int i = 0;i <= N;i++)  
    {  
        f[i][0] = 0;  
    }  
    for (int v = 0;v <= V;v++)  
    {  
        f[0][v] = 0;  
    }  
    //递推  
    for (int i = 1;i <= N;i++)  
    {  
        for (int v = Weight[i];v <= V;v++)  
        {  
            f[i][v] = 0;  
            nCount = min(Num[i],v/Weight[i]);//是当前背包容量v,而不是背包的总容量  
            for (int k = 0;k <= nCount;k++)  
            {  
                f[i][v] = max(f[i][v],f[i - 1][v - k * Weight[i]] + k * Value[i]);  
            }  
        }  
    }  
    return f[N][V];  
}  

`B---普通拆分---直接对每一件物品进行拆分成min(Num[i],V/Weight[i])件,之后在拆分后的集合上进行01背包的求解。时间复杂度:和基本思路一样,没有降低。

 

C---二进制拆分---对每i件物品,拆分的策略为:新拆分的物品的重量等于1件,2件,4件,..,(2^(k - 1)),Num[i] - (2^(k - 1))件,其中k 是满足Num[i] - 2^k + 1 > 0 的最大整数。

(1)最后一个物品的件数的求法和前面不同,其直接等于 该物品的最大件数 - 前面已经分配之和。

(2)分成的这几件物品的系数和为Num[i],表明第i种物品取的件数不能多于Num[i]。

举例:某物品为13件,则其可以分成四件物品,其系数为1,2,4,6.这里k = 3。

当然,这里使用二进制的前提还是使用二进制拆分能保证对于0,,,Num[i]间的每一个整数,均可以用若干个系数的和表示。

具体使用时,有一个小优化,即:

我们不对所有的物品进行拆分,因此物品一旦拆分,其物品个数肯定增加,那么复杂度肯定上去。

此时,我们可以选择性地对物品进行拆分:

(1)如果第i个物品的重量Weight[i] * 物品的个数Num[i] >= 背包总重量V,可以不用拆分。

(2)如果第i个物品的重量Weight[i] * 物品的个数Num[i] < 背包总重量V,可以不用拆分。

其实,拆不拆分,就看该物品能不能满足完全背包的条件。即,看该物品能不能无限量供应。

解释:为啥满足Weight[i] * 物品的个数Num[i] >= 背包总重量V的物品可以不用拆分?

此时,满足该条件时,此物品原则上是无限供应,直到背包放不下为止。

最终,对于不需要拆分的物品,可以看出完全背包的情况,调用处理完全背包物品的函数。对于需要拆分的物品,可以看出01背包的情况,调用处理01背包物品的函数。

这样,由于不对满足完全背包的物品进行拆分,此时物品个数就没有对所有物品拆分时的物品个数多,即程序中外层循环降低,复杂度也就下去了。

int f[V + 1] = {0};  
/* 
f[v]:表示把前i件物品放入容量为v的背包中获得的最大收益。 
f[v] = max(f[v],f[v - Weight[i]] + Value[i]); 
v的为逆序 
*/  
void ZeroOnePack(int nWeight,int nValue)  
{  
    for (int v = V;v >= nWeight;v--)  
    {  
        f[v] = max(f[v],f[v - nWeight] + nValue);  
    }  
}  
  
/* 
f[v]:表示把前i件物品放入容量为v的背包中获得的最大收益。 
f[v] = max(f[v],f[v - Weight[i]] + Value[i]); 
v的为增序 
*/  
void CompletePack(int nWeight,int nValue)  
{  
    for (int v = nWeight;v <= V;v++)  
    {  
        f[v] = max(f[v],f[v - nWeight] + nValue);  
    }  
}  
  
int MultiKnapsack()  
{  
    int k = 1;  
    int nCount = 0;  
    for (int i = 1;i <= N;i++)  
    {  
        if (Weight[i] * Num[i] >= V)  
        {  
            //完全背包:该类物品原则上是无限供应,  
            //此时满足条件Weight[i] * Num[i] >= V时,  
            //表示无限量供应,直到背包放不下为止.  
            CompletePack(Weight[i],Value[i]);  
        }  
        else  
        {  
            k = 1;  
            nCount = Num[i];  
            while(k <= nCount)  
            {  
                ZeroOnePack(k * Weight[i],k * Value[i]);  
                nCount -= k;  
                k *= 2;  
            }  
            ZeroOnePack(nCount * Weight[i],nCount * Value[i]);  
        }  
    }  
    return f[V];  
}  

 

© 著作权归作者所有

共有 人打赏支持
上一篇: 完全背包
下一篇: stl string常用函数
曾劲松
粉丝 5
博文 200
码字总数 141434
作品 0
武汉
私信 提问

暂无文章

OSChina 周一乱弹 —— 加油,还有11个小时就下班了

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @_全村的希望 :吴亦凡把大碗面正儿八经做成单曲了,你别说,还挺好听 《大碗宽面》- 吴亦凡 手机党少年们想听歌,请使劲儿戳(这里) @tom_t...

小小编辑
27分钟前
53
7
C++ vector和list的区别

1.vector数据结构 vector和数组类似,拥有一段连续的内存空间,并且起始地址不变。 因此能高效的进行随机存取,时间复杂度为o(1); 但因为内存空间是连续的,所以在进行插入和删除操作时,会造...

shzwork
今天
6
0
Spring之invokeBeanFactoryPostProcessors详解

Spring的refresh的invokeBeanFactoryPostProcessors,就是调用所有注册的、原始的BeanFactoryPostProcessor。 相关源码 public static void invokeBeanFactoryPostProcessors(Configu......

cregu
昨天
5
0
ibmcom/db2express-c_docker官方使用文档

(DEPRECIATED) Please check DB2 Developer-C Edition for the replacement. What is IBM DB2 Express-C ? ``IBM DB2 Express-C``` is the no-charge community edition of DB2 server, a si......

BG2KNT
昨天
4
0
Ubuntu 18.04.2 LTS nvidia-docker2 : 依赖: docker-ce (= 5:18.09.0~3-0~ubuntu-bionic)

平台:Ubuntu 18.04.2 LTS nvidia-docker2 版本:2.0.3 错误描述:在安装nvidia-docker2的时候报dpkg依赖错误 nvidia-docker2 : 依赖: docker-ce (= 5:18.09.0~3-0~ubuntu-bionic) 先看一下依......

Pulsar-V
昨天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部