多重背包问题的三种复杂度解法，O(n * w * c)、O(n*w*log c)和O(n * w)。

时间：2021-05-07 18:41:42

吹水：

初一的时候就遇到了要求快速解决多重背包问题的题目，当时没有总结的习惯，结果最近遇到的时候还有些懵，感觉基础不是很牢固，需要巩固一下，在这里写一下自己对题目中的两种做法的理解。

O（n * w *c）解法:

相信不用解释这个解法大家都懂，之所以列出来是为了作为后面的参考。

#define fo(i, x, y) for(int i = x; i <= y; i ++)
#define fd(i, x, y) for(int i = x; i >= y; i --)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
using namespace std;

const int Maxn = 1005, Maxm = 1005;
int n, m, w[Maxn], v[Maxn], c[Maxn], f[Maxm + 1];

int main() {
    freopen("a.in", "r", stdin);
scanf("%d", &n);
    fo(i, 1, n) scanf("%d %d %d", &w[i], &v[i], &c[i]);
    fo(i, 1, n) {
        fd(j, Maxm, w[i])
            fo(k, 1, min(c[i], j / w[i]))
                f[j] = max(f[j], f[j - k * w[i]] + k * v[i]);
    }
scanf("%d", &m); printf("%d", f[m]);
}

O(n*w*log c)解法：

先解释一下：n是物品个数，w是weight，即物体所占的份额，c就是物体可以有多少个。
对于当前的物品，若它能使用的个数为c，k是最大的正整数且满足 2k+1<=c （ k=⌊logc2⌋ -1），y = c−(2k+1−1) 。
我们可以把原来可以用c次的物品拆分成k+2个只能用一次的物品。
前k+1个物品分别是: wi=w∗2i,vi=c∗2i,ci=1(0<=i<=k)
第k+2个物品是： w′=w∗y,v′=v∗y,c′=1
转换成了01背包问题。
这样子，我们充分利用了二进制的原理，可以刚好表示出用了次数为0-c的原物品。

#include<cstdio>
#define fo(i, x, y) for(int i = x; i <= y; i ++)
#define fd(i, x, y) for(int i = x; i >= y; i --)
#define max(a, b) ((a) > (b) ? (a) : (b))
using namespace std;

const int Maxn = 1005, Maxm = 1005;
int n, m, a2[35], w[Maxn], v[Maxn], c[Maxn], f[Maxm + 1];

int main() {
    freopen("a.in", "r", stdin);
    a2[0] = 1; fo(i, 1, 30) a2[i] = a2[i - 1] * 2;
scanf("%d", &n);
    fo(i, 1, n) scanf("%d %d %d", &w[i], &v[i], &c[i]);
    fo(i, 1, n) {
int k = log2(c[i]);
        fo(z, 0, k)
            fd(j, Maxm, a2[z] * w[i])
                f[j] = max(f[j], f[j - a2[z] * w[i]] + a2[z] * v[i]);
int y = c[i] - a2[k];
        fd(j, Maxm, y * w[i])
            f[j] = max(f[j], f[j - y * w[i]] + y * v[i]);
    }
scanf("%d", &m); printf("%d", f[m]);
}

O(n * w)做法：

这已经是一个线性做法了，用了单调队列。
让我们观察一下暴力的dp式(为了方便，下面的除号全部默认下取整)：
fi=max(f′i−j∗w+j∗v)(1<=j<=min(c,j/w))
等价于 fi=max(f′k+(i−k)/w∗v)(k=i(mod w)) and ((i−k)/w<=c)
于是我们可以想到以(i % w)为关键字开w条单调队列辅助dp。
对于每一条队列，最方便的是存已占的份额（w）值，若队列中有两个x,y,且(x <ｙ)，则必须满足:
fx+(y−x)/w∗v>=fy
且队列头start对于当前的i必须满足 (i−start)/w<=c 。
也许我们还需要一个滚动数组。

Code:

#include<cstdio>
#define fo(i, x, y) for(int i = x; i <= y; i ++)
#define max(a, b) ((a) > (b) ? (a) : (b))
using namespace std;

const int Maxn = 1000005, Maxm = 1000005;

int n, m, o, w[Maxn], v[Maxn], c[Maxn], f[2][Maxm + 1];
int d[Maxn];

int main() {
scanf("%d", &n);
    fo(i, 1, n) scanf("%d %d %d", &w[i], &v[i], &c[i]);
    fo(i, 1, n) {
        o = !o;
        fo(mo, 0, w[i] - 1) {
int st = 1, en = 0;
            fo(j, 0, max(0, (Maxm - mo) / w[i])) {
int k = mo + j * w[i];
while(st <= en && (k - d[st]) / w[i] > c[i]) st ++;
while(st <= en && f[!o][d[en]] + (k - d[en]) / w[i] * v[i] < f[!o][k]) en --;
                d[++ en] = k;
if(st <= en) f[o][k] = f[!o][d[st]] + (k - d[st]) / w[i] * v[i]; else f[o][k] = 0;
            }
        }
    }
scanf("%d", &m); printf("%d\n", f[o][m]);
}

总结：

其实log算法在小数据中比队列算法还要快，因为常数小，所以比赛时看数据而定吧。

标签：

相关文章