首页
登录 | 注册

多重背包:经典DP问题( 基本/二进制优化/单调队列优化 )

目录

基本方法

**二进制优化

*****单调队列优化


多重背包问题描述:介于01背包和完全背包问题之间,每种物品的最大选取数目都是已知的。

对于一定数量( i )的物品有一个容量为( j )的背包,每个物品都有自己的容量( k )、价值(value)和数目( cnt )。在保证物品容量之和不大于背包容量的前提下,如何选取物品得到最大价值?


基本方法:

*NEW*:测试题链接(基本方法)

状态转移方程可以稍微修改完全背包问题的得到,dp[ind][jnd]=Max(dp[ind-1][jnd-knd*k]+knd*value,dp[ind-1][jnd]),原方程不变,需要改的是knd的范围,完全背包每个物品的个数是无限个,knd仅需要满足knd*k<=jnd。现在每个物品有了自己的最大数目( cnt ),也就是说还需要满足knd<=cnt。

经过上面的推论,在 jnd<k 时,dp[ind][jnd]=dp[ind-1][jnd] ;jnd>=k时,dp[ind][jnd]=Max(dp[ind-1][jnd-knd*k]+knd*value,dp[ind-1][jnd]) | knd<=cnt | knd*k<=jnd 。

#include <stdio.h>
#define Max(a, b) (a > b ? a : b)
int dp[1005][10005];
int k[1005], value[1005], cnt[1005];
int main(int argc, char *argv[])
{
    int i, j, s;
    scanf("%d %d", &i, &j);
    for (int ind = 1; ind <= i; ++ind)
        scanf("%d %d %d", &k[ind], &value[ind], &cnt[ind]);
    for (int ind = 1; ind <= i; ++ind)
    {
        for (int jnd = 1; jnd <= j; ++jnd)
        {
            if (jnd - k[ind] < 0)
                dp[ind][jnd] = dp[ind - 1][jnd];
            else
            {
                s = dp[ind - 1][jnd];
                for (int knd = 1; knd * k[ind] <= jnd && knd <= cnt[ind]; knd++)
                    s = Max(s, dp[ind - 1][jnd - knd * k[ind]] + knd * value[ind]);
                dp[ind][jnd] = s;
            }
        }
    }
    printf("%d\n", dp[i][j]);
    return 0;
}

**二进制优化

*NEW*:测试题链接(须二进制优化)

不经优化的状态转移方程直接求解时间复杂度太高,大多需求都不能满足。考虑能不能通过什么方法进行优化,首先想到的是能在01背包和完全背包问题中用到的一维滚动数组方法。多重背包问题介于这两者之间,根据上面的状态转移方程推导可以得出当cnt的值满足( cnt*k>=j )的时候,可以认为这个物品是有无限个的,因为全部用这个物品来装背包数量也够用,于是这种情况可以用完全背包的滚动数组法解决。( cnt*k<j )时物品肯定是有限个的,可以认为它们是一个个单个物品,挨个用01背包滚动数组法解决,但是这么做时间复杂度就太高了。这里考虑用二进制来表示物品的个数,因为二进制可以分解任意正整数,比如说数字 7 可以二进制分解成 1+2+4 、13 = 1+2+4+6 。从1开始分解,直到不够分出一个2的指数为止,补上剩余的数就是分解的结果,为什么这样做呢?

用分解的数( I )各自代表一个物品,它们是原物品重量和价值的 I 倍,挨个01背包处理,时间被大大优化。再者,分解出来的数通过选择或不选可以组合成任意一个 0~cnt 的数,而且又保证了 0 会是能组合出来的最小数,cnt 是能组合出来的最大数。出来的结果会和不经优化的完全一样。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define Max(a, b) (a > b ? a : b)
#define ArrayMax 10005
int dp[ArrayMax];
int main(int argc, char *argv[])
{
    int i, j;
    scanf("%d %d", &i, &j);
    while (i--)
    {
        int k, value, cnt;
        int now = 1;
        scanf("%d %d %d", &k, &value, &cnt);
        if (cnt * k >= j)
        {
            for (int ind = k; ind <= j; ind++)
                dp[ind] = Max(dp[ind - k] + value, dp[ind]);
        }
        else
        {
            while (1)
            {
                if (cnt > now)
                {
                    cnt -= now;
                    for (int ind = j; ind >= k * now; ind--)
                        dp[ind] = Max(dp[ind - k * now] + now * value, dp[ind]);
                    now *= 2;
                }
                else
                {
                    now = cnt;
                    for (int ind = j; ind >= now * k; ind--)
                        dp[ind] = Max(dp[ind - now * k] + now * value, dp[ind]);
                    break;
                }
            }
        }
    }
    printf("%d\n", dp[j]);
    return 0;
}

*****单调队列优化

*NEW*:测试题链接(须单调队列优化)

dp[ind][jnd]=Max(dp[ind-1][jnd-knd*k]+knd*value,dp[ind-1][jnd]) | knd<=cnt | knd*k<=jnd 再拿出上面写出来的状态转移方程看看,观察如何减少重复运算?

  • 当背包最大容量是 10 ,当前物品容量 3 价值 4 数量 3 。走一遍现在状态转移方程
  • 当前背包容量3    dp[3]  dp[3-1*3]+1*4  ( 最多放一个,两个值取最大值 )
  • 当前背包容量4    dp[4]  dp[4-1*3]+1*4  ( 同上 )
  • 当前背包容量5    dp[5]  dp[5-1*3]+1*4  ( 同上 )
  • 当前背包容量6    dp[6]  dp[6-1*3]+1*4  dp[6-2*3]+2*4  ( 最多放两个,三个值取最大值 )
  • 当前背包容量7    dp[7]  dp[7-1*3]+1*4  dp[7-2*3]+2*4  ( 同上 )
  • 当前背包容量8    dp[8]  dp[8-1*3]+1*4  dp[8-2*3]+2*4  ( 同上 )
  • 当前背包容量9    dp[9]  dp[9-1*3]+1*4  dp[9-2*3]+2*4  dp[9-3*3]+3*4  ( 最多放三个,四个值取最大值 )
  • 当前背包容量10  dp[10]  dp[10-1*3]+1*4  dp[10-2*3]+2*4  dp[10-3*3]+3*4  ( 同上 )

可以发现对每个容量背包计算时,都是取多个数的最大值,而且数的个数是能放进当前物品的最大值加一。每一项中 dp[] 有很多是重复的,但是 dp[] 重复时,后面的常数项却并不重复,于是可以考虑对每组背包的数据都减去一个常数,取到最大值后再加回来,就可以在保证结果不变的同时,出现许许多多的重复项

每个背包容量的数减去当前背包放最大当前物品时的价值

  • 当前背包容量0    dp[0]  ( 一个也放不了 )
  • 当前背包容量1    dp[1]  ( 同上 )
  • 当前背包容量2    dp[2]  ( 同上 )
  • 当前背包容量3    dp[3]-1*4  dp[3-1*3]  ( 最多放一个,减去1*4 )
  • 当前背包容量4    dp[4]-1*4  dp[4-1*3]  ( 同上 )
  • 当前背包容量5    dp[5]-1*4  dp[5-1*3]  ( 同上 )
  • 当前背包容量6    dp[6]-2*4  dp[6-1*3]-1*4  dp[6-2*3]  ( 最多放两个,减去2*4 )
  • 当前背包容量7    dp[7]-2*4  dp[7-1*3]-1*4  dp[7-2*3]  ( 同上 )
  • 当前背包容量8    dp[8]-2*4  dp[8-1*3]-1*4  dp[8-2*3]  ( 同上 )
  • 当前背包容量9    dp[9]-3*4  dp[9-1*3]-2*4  dp[9-2*3]-1*4  dp[9-3*3]  ( 最多放三个,减去3*4 )
  • 当前背包容量10  dp[10]-3*4  dp[10-1*3]-2*4  dp[10-2*3]-1*4  dp[10-3*3]  ( 同上 )

相同颜色项是相同的,可以看到有很多重复项,当背包总容量能放下很多当前物品时,重复项会很多。根据这个方法改进状态转移方程,设背包放下最大可容量个数的物品后剩余容量( ind = j%k ),

状态转移方程得到:dp[i][j] = Max(dp[i-1][ind+jnd*k]-jnd*value+jnd*value , dp[i-1][j])

                                ( j/k-cnt<=jnd<=j/k )

jnd代表的意思是当前背包比可以放当前背包的数量少几,如果最多放3个当前物品,那么jnd可以是0~3。然而到此为止并没有进行实质性的优化,因为只是改变了状态转移方程使之出现许多重复项,如何重复使用这些重复项呢?那就是使用单调队列!我们先从上面的例子中取出ind相同的,如当前背包容量是3、6、9的。

  • 当前背包容量0    dp[0]
  • 当前背包容量3    dp[3]-1*4  dp[0]
  • 当前背包容量6    dp[6]-2*4  dp[3]-1*4  dp[0]
  • 当前背包容量9    dp[9]-3*4  dp[6]-2*4  dp[3]-1*4  dp[0]

使用从大到小的单调队列对上面三个背包容量求最大值,当背包容量是0,求得dp[0]存入单调队列中,当前最大值显然是刚存进去的队首dp[0],取出后加上0*value( 这里的0是指容量0的背包最大可取当前物品数量j/k )。以此类推,单调队列的队首总是当前刚入队的值和之前所有队中元素的最大值,取出加上j/k即可。每个容量的背包需要完成的操作就是入队然后取队首

到此还有种情况没有考虑到,将上面例子中背包最大容量调整至12时,存在下面的组合

  • 当前背包容量12  dp[12]-4*4  dp[9]-3*4  dp[6]-2*4  dp[3]-1*4  dp[0]

然而此时背包可选项是前四项,最后的 dp[0] 是取四个当前物品的对应项,然而cnt限制最多取3个当前物品,所以还需要进行的一个额外操作是将超出限制的队首出栈。至于为什么每次出队只可能有一个,因为每次单调队列入队时都将当前元素放在队尾,它前面的元素数值肯定比他都大,且下标都小于它的下标

也就是说一组在ind相同时,jnd从0~(m-ind)/k递增,求得每个jnd对应的 dp[jnd*k+ind]-jnd*value 项,单调队列入队后检查队首下标是否超出cnt的限制,超出则将队首出队,最后取队首加上 jnd*value 赋值给原来的dp[j],也就是改变状态转移方程后的 dp[jnd*k+ind] 。

外面再遍历可能的 ind 值,0<=ind<k。完成单调队列优化的多重背包问题!

#include <stdio.h>
#include <stdlib.h>
#define arraymax 20001
#define Max(a, b) (a > b ? a : b)
int dp[arraymax];
int book[arraymax], que[arraymax];
int main(int argc, char *argv[])
{
    int n, m;
    scanf("%d%d", &n, &m);
    while (n--)
    {
        int k, value, cnt;
        scanf("%d%d%d", &k, &value, &cnt);
        if (cnt * k >= m)
        {
            for (int ind = k; ind <= m; ind++)
                dp[ind] = Max(dp[ind - k] + value, dp[ind]);
        }
        else
        {
            for (int ind = 0; ind < k; ind++)
            {
                int head = 0, body = 0;
                for (int jnd = 0; jnd <= (m - ind) / k; jnd++)
                {
                    int y = dp[jnd * k + ind] - jnd * value;
                    while (head < body && y >= que[body - 1])
                        body--;
                    book[body] = jnd;
                    que[body++] = y;
                    if (book[head] < jnd - cnt)
                        head++;
                    dp[jnd * k + ind] = que[head] + jnd * value;
                }
            }
        }
    }
    printf("%d\n", dp[m]);
    return 0;
}

上面写出的三种做法,时间复杂度是依次减少的,在51nod上的多重背包模板题测试得出。( 链接地址 )

基本法超时( >1000ms )( 约O(n*m*cnt) ),二进制优化法在62ms左右( 约O(n*m*log(cnt)) ),单调队列优化法可以达到15ms左右( 约O(n*m) ),以此可以看出单调队列优化后的DP是多么的犀利。

 

END


相关文章

  • 贾扬清:我对人工智能方向的一点浅见
    阿里妹导读:作为 AI 大神,贾扬清让人印象深刻的可能是他写的AI框架Caffe ,那已经是六年前的事了.经过多年的沉淀,成为"阿里新人"的他,对人工智能又有何看法?最近,贾扬清在阿里内部分享了他的思考与洞察,欢迎共同探 ...
  • 现如今,六西格玛设计管理的知名度是越来越高了,很多企业为了能够更好的发展,开始选择实施六西格玛设计管理,并且已经有企业成功的检验推行六西格玛设计管理会给企业带来显着的成效.那么,六西格玛设计在研发管理中是怎么应用的? 六西格玛设计管理 1. ...
  • 六西格玛设计DFSS在研发管理中是怎么应的
    六西格玛设计DFSS在研发管理中是怎么应用的? 现如今,六西格玛管理的知名度是越来越高了,很多企业为了能够更好的发展,开始选择实施六西格玛管理,并且已经有企业成功的检验推行六西格玛管理会给企业带来显着的成效.那么,六西格玛设计在研发管理中是 ...
  • CODING 研发管理系统上线全球加速,助力企业跨区域协作
    CODING 研发管理系统现已全面支持全类型代码仓库的 全球加速访问. 随着国内互联网红利的日趋枯竭与全球互联网的加速普及.越来越多的企业开始走出国门,将目光投向全世界,搭建跨国体系.跨出国门的中国企业在选择服务时,首要考虑国内的速度和可靠 ...
  • 微软发布人工智能教育与学习共建社区
    步入2019,人工智能(Artificial Intelligence)的浪潮依然汹涌,各国对于AI人才的需求进一步加大:2月,美国总统特朗普签署行政命令,正式启动美国人工智能计划:加拿大正通过"全球技能战略签证"吸引国 ...
  • 云原生的新思考,为什么容器已经无处不在了
    4月24日,中国信息通信研究院主办的首届云原生产业大会在北京举行,在<云原生数字引领未来>的主题演讲中,阿里云容器服务总监易立表示:"云原生不但可以很好的支持互联网应用,也在深刻影响着新的计算架构.新的智能数据应用.以 ...

2020 jeepshoe.net webmaster#jeepshoe.net
13 q. 0.261 s.
京ICP备10005923号