背包问题

01背包:
每件物品都有它的价值和体积,你的背包有一定容量,如何能获取最大价值?

第一行有

这时dalao们就发现问题了,若有5000件物品背包容量是100000,就爆空间了,这怎么办呢?

我们可以想一个问题,如果用15的空间既可以获得10的价值也可以获得50的价值,那么你选哪个?

都选50的吧

那么获得10价值的方案还有用吗?

显然没有用了

所以我们只需要记录每一个容积所能获得的最大价值就好了,这样就可以压缩成为一维,从而舍弃第一维,只要容积那一维(只储存最大的价值)

$一层循环枚举每一个物品$

$二层循环枚举可用的最大体积$

$如果能装下$

$f[v]=max(f[v],f[v-w[i]]+c[i]);$

$否则//自己等于自己,当然没必要写这句$

完全背包:
每件物品都有它的价值和体积但每件物品可以无限拿,你的背包有一定容量,如何能获取最大价值?

第一行有

$很显然,每种物品可以拿无数件$

$当然你也可以不拿$

$如果拿(前提是有足够空间),就相当于背包少了v[i]的体积,多了c[i]的价值,$

$不拿的话(没有空间)就是上一个物品占用当时最大的体积的价值$

$我们先讲一种便于理解的方法,即: 加一重循环枚举个数k$

$当然,依然不能超出背包限制$

$状态转移方程f[v] = max{ f[v],f[ j - k*v[i]]+k* c[i]};$

$这应该每位dalao和像我一样的蒟蒻都能明白吧$

$然后明白了就可以上一种玄学一的点了$

$一层循环枚举每一个物品$

$二层循环枚举可用的最大体积$

$如果能装下(c代表价值v代表枚举体积)$

$f[v]=max(f[v],f[v-w[i]]+c[i]);$

$注意,枚举的v是指最大占用v体积的情况下获得最大的价值$

$v一定要正着枚举(从1开始到最大体积结束)$

$因为完全背包可以无限选,你在选择v-w[i]时,他就有可能已经选过了.$

$到这里有些像我一样的蒟蒻就不懂了$

$我举一个生动形象的例子$

$背包容量为5$

$有1个物品,体积为2,价值为3(这么简单的例子不是因为我懒)$

$从5开始呢?$

$f[5]=f[5-2]+3;$

$f[4]=f[4-2]+3;$

$f[3]=f[3-2]+3;$

$f[2]=f[2-2]+3;$

$1和0不行$

$可以看出,从5到2,关系分别是$

$由3推5$

$由2推4$

$由1推3$

$由0推2$

$从一开始推出来的5开始没有被用过的再被利用$

$从1开始呢?$

$1和0不行$

$f[2]=f[2-2]+3;$

$f[3]=f[3-2]+3;$

$f[4]=f[4-2]+3;$

$f[5]=f[5-2]+3;$

$可以看出,从5到2,关系分别是$

$由0推2$

$由1推3$

$由2推4$

$由3推5$

可以看出:

由0推出的2又在推4的时候用到了,这就实现了完全背包

大家应该可以发现我在写01背包和完全背包时有很多相同之处

这是因为01背包是一种特殊的完全背包

好啦,一篇博客结束啦

emmm...怎么能结束了呢,我又来更新博客啦,

二维费用背包,

即有两个限制,比如,一件物品既有体积又有质量,你不能超出2者其中一个,求最大价值

明白了01背包和完全背包之后,这个问题就简单许多

假如一种限制也没有呢?

代码应该是

    for(k=1; k<=c; k++) {
        ans=max(a[k]+ans,ans);
    }

加一种限制呢?(即只有体积限制)

    for(k=1; k<=c; k++) {
        for(i=n; i>=v[k]; i--) {
              a[i] = max(a[i-v[k]]+jz[k],a[i][j]);
        }
    }

区别是什么?

加了一层循环,又加了一维的空间

由此推出

    for(k=1; k<=c; k++) {
        for(i=n; i>=v[k]; i--) {
            for(j=m; j>=w[k]; j--) {
                    a[i][j] = max(a[i-v[k]][j-w[k]]+jz[k],a[i][j]);
            }
        }
    }

合情合理又简单.

多重背包问题

即一个物品可以拿指定的次数(这才是正常的日常问题)

还是先考虑简单的情况

转换01背包(硬转换)

再加一层循环枚举个数,不能超过背包容量

    for(k=1; k<=c; k++) {
        for(i=n; i>=v[k]; i--) {
            for(j=1; j<=c[i]; j++) {
                    a[i] = max(a[i-j*w[k]]+j*jz[k],a[i]);
            }
        }
    }

这样就连我这样的蒟蒻也明白吧

接下来就要上一种更厉害的方法了

3=1+2

这个式子每个人都会吧

转换2进制 11=1+10

那若给你1,10,100,1000,10000.....

这些二进制数,是不是能凑出所有的数呢?

任何一个二进制数每一位要么0,要么1,所以都能凑出来

举个栗子

假如二进制第3位是1那么就加上1000,如果是0就不加

好啦回归正题

1,10,100,1000,10000.....

转换10进制: 1,2,4,8....

也就是说,我们不需要每个都枚举,假如有一个物品可以拿10个,那我们只需要将1,2,4,3这几种情况跑一遍01就好了

可能还是有像我这样的蒟蒻看不懂,我来证明一下(看的别的dalao的证明方法)

如果我们要凑的数n小于等于2^k(k是能拆最大的二进制数以10为例,k就是2)转换二进制直接凑都明白吧

如果n大于2^k怎么办呢?

我们先想一个问题,假如你有2这个数,并且能凑出4这个数,那么是不是也能凑出4+2呢?

如果要凑n,我们可以先凑n-2^k,n-2^k肯定能凑出,而2^k也能凑出,那么n就能凑出

转换部分

    for(i=1; i<=n; i++) {
        scanf("%d%d%d",&w[i],&v[i],&s);
        for(j=1; j<=s; j*=2) {
            w[++k] = w[i]*j;
            v[k] = v[i]*j;
            s-=j;
        }
        if(0!=s) {
            w[++k] = w[i]*s;
            v[k] = v[i]*s;
        }
    }

分组背包:

有好多组物品,每组只能拿一个物品,使总价值最大

其实这个很简单,只需要再加一层循环枚举组,使组内物品在不超出当前背包容积的情况下价值最大就好啦

    int zd2=0; 
    for(i=1; i<=zd; i++) {//枚举组
        for(j=m; j>=1; j--) {//枚举空间
            for(p=b[1].k ; p>=1; p--) {//枚举组内每一物品
                if(w[b[i].bb[p]]<=j){//如果能装下
                    if(zd2<a[j-w[b[i].bb[p]]]+v[b[i].bb[p]])//找最大的
                        zd2=a[j-w[b[i].bb[p]]]+v[b[i].bb[p]];
                } 
                    
            }
            a[j]=max(a[j],zd2);//在和原先的比较就好了
            zd2=0;
        }
    }

注意:最好不要在找最大时就对a[]做手脚,否则可能出错(可以自己想下为什么)

当然,大家看到这个代码肯定一脸懵,我在讲一下预处理

这是定义的结构体

struct po {
    int bb[1001];//存放组内每一个物品的序号
    int k;//有多少物品(组内)
};
po b[101]= {0};//组

输入部分:

for(i=1; i<=n; i++) {
        scanf("%d%d%d",&w[i],&v[i],&zu);
        b[zu].bb[++b[zu].k] = i;//组内下一个物品编号
        if(zd<zu)//找出有多少组
            zd=zu;
    }

更新完啦!！!

时隔几个月，我又来更新了....

至于树形背包,前提是先学会分组背包

以洛谷p2014选课为例

设dp[x][i]为以x为根的子树,花i代价最大的价值,对于x的子树都是叶子节点的情况应该很好理解

大家可以手动画一下图,这种情况很简单,但问题是一般情况我们要解决的并不是这种问题

假设我们正在计算dp[x][k],树根的费用是m

我们必须要选树根,因为树根不选是无法选儿子的

那么我们只需要计算出所有子树中加起来费用是k - m的最大价值