T1.Coins(POJ1742)

多重背包最基本的状态转移方程是这样的: 用 f[i][j] 表示前 i 个物品装进背包占容量为 j 时的最大价值。
$$

题意:

求用 n 种硬币每种 c[i] 个最多可以凑出多少种面额?

二进制优化:

作为将 $O(NV\sum{\frac{V}{w[i]}})$也就是 $O(N^2V)$级别的算法优化成 $O(V\sum{log(c[i])})$的方法,自然少不了对”2″ 灵活的应用。
由于这种方案的优化效果不是非常好,无法顺利通过本题,而且大家肯定已经可以熟练运用,这里暂不讨论。


单调队列优化:

$O(K\times logN)$的算法再经过某些基于单调性的脑洞级优化后,会变成惊人的 $O(K\times 1)$而这道题用到的当然就是这种方法。
观察 f[i][j] 是由哪些东西的最小值转移过来的:

所以,对于这道题,我们要知道的就是红色格子里有没有可以达到的容量。而红色格子是连续的最多 c[i] 个。
这不是 so-easy 的东西吗?

下面具体介绍几种解决方法:

1.

我们建立一个假的队列,这个队列有队首和队尾,但是没有队列元素。
现在我们从 f[i-1][0] 向 f[i-1][j] 每隔 w[i] 个将那个数添加到队列中,用队列记录队首到队尾的和。这样对于 f[i][j],队列中的所有元素的和就是我们图片中红色格子的和。

2.

不用建立队列,并且将方程的维数降为 1 维。这时转移方程就是:(f[j] 表示达成 j 容量的方案数。)

for(int i=1;i<=n;i++)
{
    for(int j=v[i];j<=V;j++)
        f[j]=f[j]+f[j-v[i]];
    for(int j=v[i];j<=V;j++)
        if(j-(c[i]+1)*w[i]>=0)f[j]-=f[j-(c[i]+1)*w[i]];
}

这就是完全背包的做法再减去不应该装的物品的做法。程序结束后 f[i] 数组里留下来的就是达成 i 容量的方案数。但是由于第二层循环需要 2 次,这种方法还是会莫名其妙就 TLE。。。

3.

借鉴于第二种方法,我们可以再开辟一个数组 s[j] 表示 f[j] 是装了多少件 i 物品从而变为可行的。总之这样就可以 AC

for(srg int i=1;i<=n;i++)
{
    memset(s,0,sizeof(s));
    for(srg int j=v[i];j<=mv;j++)
    {
        if(!f[j]&&f[j-v[i]]&&s[j-v[i]]<c[i])
        {
            ++tot;
            f[j]=1;
            s[j]=s[j-v[i]]+1;
        }
    }
}

那么我通过此题的代码如下:(应用了诸多卡常技巧)

#include <iostream>
#include <cstdio>
#include <cstring>

#define MX 110
#define srg register

using namespace std;

int v[MX],c[MX];
int f[100010];
int s[100010];
int n,mv,tot;

int main()
{
    while(scanf("%d %d", &n, &mv) && n && mv >= 0)
    {
        for(srg int i=1;i<=n;i++)scanf("%d",&v[i]);
        for(srg int i=1;i<=n;i++)scanf("%d",&c[i]);
        for(srg int i=0;i<=mv;i++)f[i]=0;
        f[0]=1,tot=0;
        for(srg int i=1;i<=n;i++)
        {
            memset(s,0,sizeof(s));
            for(srg int j=v[i];j<=mv;j++)
                if(!f[j]&&f[j-v[i]]&&s[j-v[i]]<c[i])
                    ++tot,f[j]=1,s[j]=s[j-v[i]]+1;
        }
        printf("%d\n",tot);
    }
    return 0;
}




T2. 多重背包 (HDU2191)

题意:

给定一些物品的价值、大小、数量。求一个大小为 m 的背包最多装得下多少价值的物品。

虽然这道题乱搞都可以 AC,但是我们还是实用单调队列优化

这里的 f[i] 表示容量为 i 的背包可以装下的最大价值 (而不是恰好装下)。因此可以很方便地使用单调队列优化
这所谓的单调队列是神码样的呢?它其实维护了两个单调性:
右边的比左边的新进队。
左边的比右边的优。
为什么这样就对呢?其他单调性为什么不对呢?
这样想:我们至少得维护时间的单调性:也就是右边的比左边的新进队。为什么同时左边的要比右边的优呢?感性地想:在队列中的元素向左侧 “流动” 时,我们会 “失去” 非常优秀的解而只能从新进来的解中转移。因此单调性是左边优于右边。
有了单调队列的思路,有了状态转移方程,我们就可以轻松的写出代码。
噢,不知道大家有没有想到这样一个问题:
由于状态转移方程是:
f[i]=max(f[i-kw[i]]+kv[i])
我们不能直接将每个 f[i] 的值存进队列,而应该保存 f[i]-i/w[i]*v[i](仔细想一想为什么)
有了以上这些准备工作,我们的程序差不多就完备了。

#include <iostream>
#include <cstdio>
#include <cstring>

#define max(a,b) ((a>b)?(a):(b))
#define MX 101

using namespace std;

int v[MX],w[MX],c[MX];
int n,m;

void input()
{
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d%d",&w[i],&v[i],&c[i]);
}

pair<int,int>q[MX];
int h,t;
int f[MX];

void work()
{
    int relex;
    memset(f,0,sizeof(f));
    for(int i=1;i<=n;i++)
    {
        if(c[i]==0)continue;
        if(c[i]>m/w[i])c[i]=m/w[i];
        for(int j=0;j<w[i];j++)
        {
            h=0,t=1;
            for(int k=0;k*w[i]+j<=m;k++)             //这里我们直接枚举装入几个物品,而不是枚举装到多大空间。
            {
                relex=f[k*w[i]+j]-k*v[i];                      //要减去 k*v[i], 详见上文的分析
                while(q[h].first<relex&&h>=t)h--;
                q[++h].first=relex;
                q[h].second=k;
                while(q[t].second<k-c[i])t++;
                f[k*w[i]+j]=q[t].first+k*v[i];
            }
        }
    }
    printf("%d\n",f[m]);
}

int main()
{
    int t;
    scanf("%d",&t);
    for(int i=1;i<=t;i++)
    {
        input();
        work();
    }
    return 0;
}




T3.Bank notes(BZOJ1531 权限题)

题意:

给定一些面值的硬币和它们的数量,求凑成给定面值的最少硬币数为多少。

单调队列:

经过像 T2 那样严谨的分析,我们得出:我们需要一个单调队列维护以下单调性:
队列右侧比左侧新进入
队列左侧的元素代表的凑成的硬币数要更少
这样我们就就可以得到一份优美的代码

#include <iostream>
#include <cstring>
#include <cstdio>

#define MX 201

using namespace std;

int n,mv;
int v[MX],c[MX],f[20001];

void input()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&v[i]);
    for(int j=1;j<=n;j++)scanf("%d",&c[j]);
    scanf("%d",&mv);
}

pair<int,int> q[20001];
int h,t;

void work()
{
    int rx;
    memset(f,0x3f,sizeof(f));
    f[0]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<v[i];j++)
        {
            h=0,t=1;
            for(int k=0;k*v[i]+j<=mv;k++)
            {
                rx=f[k*v[i]+j]-k;
                while(q[h].first>rx&&h>=t)h--;
                q[++h]=make_pair(rx,k);
                while(q[t].second<k-c[i]&&h>=t)t++;
                f[k*v[i]+j]=q[t].first+k;
            }
        }
    }
    printf("%d\n",f[mv]);
}

int main()
{
    input();
    work();
    return 0;
}
分类: 文章

3 条评论

tense · 2017年7月20日 9:48 上午

f[i]=max(f[i-kw[i]]+kv[i]) 乘号

    boshi · 2017年7月21日 8:29 上午

    it disappears with no reason

【题解】 Bank notes 多重背包单调队列优化 BZOJ – 1531 | K-XZY · 2017年7月20日 10:22 上午

[…] abs 的博客讲的很好了,我也不做过多赘述:http://k-xzy.cf/?p=2009 […]

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用 * 标注