博客

写在前面

学了这么久 发出来记录一下

顺便也能巩固一下自己吧

最近又跑去看了背包九讲 然后前面都很顺利 直到多重背包Ⅲ 也就是两万的数据范围后 开始不断tle 心想着我原来能过的呀 二进制优化不就好了吗 看了评论发现是加强了数据 二进制优化是NVlog(S)的时间复杂度 算了算确实是超时的 那没办法 算法这东西 讲的不就是一个优化嘛。

看看题

有 N 种物品和一个容量是 V 的背包。

第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。

输出最大价值。

输入格式

第一行两个整数，N，V (0<N≤1000, 0<V≤20000)，用空格隔开，分别表示物品种数和背包容积。

接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。

输出格式

输出一个整数，表示最大价值。

数据范围

0<N≤1000

0<V≤20000

0<vi,wi,si≤20000

输入样例

4 5

1 2 3

2 4 1

3 4 3

4 5 2

输出样例：

10

想想办法

先算算时间复杂度 NVlog(S)=1000 * 20000 * log(20000)=3*10

⁸


然后NV肯定是没办法的 那就从log（S）下手

好 我想到这 就到此为止了 因为我不知道怎么从log（S）下手

所以我跑去学了大神们。

单调队列

我们先看下传统的

dp[i][j] = max(dp[i-1][j], dp[i-1][j-v] + w, dp[i-1][j-2

v] + 2

w,…,

dp[i-1][j-k

v] + k

w)

然后变成一维（至于怎么变成一维可以看前面背包的优化）

dp[m] = max(dp[m], dp[m-v] + w, dp[m-2

v] + 2

w, dp[m-3

v] + 3

w, …)

这里m是背包的容量 然后是对某一种物品i的最优解

我们通过对所有i进行计算与对比（循环） 就可以得出最终的最优解

然后我们这样看

dp[0], dp[v], dp[2

v], dp[3

v], … , dp[k

v]

dp[1], dp[v+1],dp[2

v+1], dp[3

v+1], … , dp[k

v+1]

dp[2], dp[v+2], dp[2

v+2],dp[3

v+2], … , dp[k

v+2]

…

dp[j], dp[v+j], dp[2

v+j], dp[3

v+j], … ,dp[k

v+j]

我们的m是等于kv+j的

所以，我们可以把 dp 数组分成 j 个类，每一类中的值，都是在同类之间转换得到的

也就是说，dp[k

v+j] 只依赖于 { dp[j], dp[v+j], dp[2

v+j], dp[3

v+j], … , dp[k

v+j] }

因为我们需要的是{ dp[j], dp[v+j], dp[2

v+j], dp[3

v+j], … , dp[k*v+j] } 中的最大值，

可以通过维护一个单调队列来得到结果。这样的话，问题就变成了 j 个单调队列的问题

所以，我们可以得到

dp[j] = dp[j] dp[j+v] = max(dp[j] + w, dp[j+v])

dp[j+2v] =max(dp[j] + 2w, dp[j+v] + w, dp[j+2v])

dp[j+3v] = max(dp[j] + 3w, dp[j+v] + 2w, dp[j+2v] + w, dp[j+3v])

…

但是，这个队列中前面的数，每次都会增加一个 w ，所以我们需要做一些转换

dp[j] = dp[j]

dp[j+v] = max(dp[j], dp[j+v] – w) + w

dp[j+2v] = max(dp[j], dp[j+v] – w, dp[j+2v] – 2w) + 2w

dp[j+3v] = max(dp[j],dp[j+v] – w, dp[j+2v] – 2w, dp[j+3v] – 3w) + 3w

…

这样，每次入队的值是 dp[j+k

v] – k

w

其实我看到这里的时候还是懵懵的 就是能感觉出来 写的好厉害 思路很顺畅 但是自己还是不明白为什么要这样写

如果你是这样的话 建议先去了解一下滑动窗口

注意事项

我们的01背包优化为一维数组是从后往前遍历的 这里我们是从前往后推的 所以要用一个新的数组去记录一下值 否则不能实现

还有就是我们的单调队列原则

代码+解析

#include <iostream>
#include <cstring>

using namespace std;

const int N = 20010; //20000的数据范围

int dp[N], pre[N], q[N]; //pre存储dp上一轮的数值结果 q表示单调队列
int n, m;

int main() {
    cin >> n >> m; //n为数量 m为容量
    for (int i = 0; i < n; ++i) {
        memcpy(pre, dp, sizeof(dp)); //数组copy
        int v, w, s;
        cin >> v >> w >> s;
        for (int j = 0; j < v; ++j) {
            /*
            head为队首位置
            tail为队尾位置
            数值越大，表示位置越后面
            队首在队尾后面队列为空，即head>tail时队列为空
            */
            int head = 0, tail = -1;
            /*
            q[]为单调队列
            存储前s个(物品数量)中的最大值
            数组从头(head)到尾(tail)单调递减
            */
            for (int k = j; k <= m; k += v) {

                //k代表假设当前背包容量为k
                //q[head]为队首元素（最大值的下标）
                //pre[]为dp[i-1][]
                //dp[]为dp[i][]
                
                /*由于滑动窗口记录的是下标，但每一个k所对应的下标都是在变
                化的。所以要根据当前的k判断窗口里存在的k对应的值包含了多少
                个v，以便于计算新的价值*/
                
                /*v的个数=(下标-余数)/v   价值=(下标-余数)/v*w
                        =(q[h]-j)/v        =(k-j)/v*w      */
                        
                /*
                维护一个大小为k的区间
                使最大值为前k个元素中最大
                (k - q[head]) / v 表示拿取物品的数量（相当于最原始的多重背包dp的k）
                */
                if (head <= tail && k - s * v > q[head])
                    ++head;
                /*
                若队内有值，该值就是前k个元素的最大值
                (k - q[head]) / v 表示拿取物品的数量（相当于最原始的多重背包dp的k）
                q[head]为队首元素（pre[]中前k个数中最大值的下标），pre[]为dp[i-1][]
                所以 pre[q[head]]为只考虑前i-1个物品时，拿前q[head]个物品的最大价值
                */
                while (head <= tail && pre[q[tail]] - (q[tail] - j) / v * w <= pre[k] - (k - j) / v * w)
                    --tail;
                /*
                若队尾元素小于当前元素，则队尾元素出队；
                若队内一个元素比当前元素小，则该元素一定不会被用到（单调队列思想）
                pre[q[tail]] + (k - q[tail]) / v * w
                与
                pre[k] - (k - j) / v * w
                分别表示队尾元素的值和当前元素的值
                */
                if (head <= tail)
                    dp[k] = max(dp[k], pre[q[head]] + (k - q[head]) / v * w);
                //去除了比当前小的元素，保证队列里的元素都比当前元素大，入队
                q[++tail] = k;
            }
        }
    }
    cout << dp[m] << endl;
    return 0;
}

时间复杂度

o(NV)

总结

很难

给到我这么多的解析和大神的代码 我还需要研究很久才能有点理解

只能祈祷并不会遇到卡二进制的多重背包吧

最后分享

最后分享给大家写大部分背包问题的板子

对于数据友好的题目很好用

#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 20010;

int n, V;
int v, w, s;
int f[N];

void zeroOnePack(int v, int w) {
    for (int j = V; j >= v; --j)
        f[j] = max(f[j], f[j - v] + w);
}

void completePack(int v, int w) {
    for (int j = v; j <= V; ++j)
        f[j] = max(f[j], f[j - v] + w);
}

void multiPack(int v, int w, int s) {
    if (s * v >= V) {
        completePack(v, w);
        return;
    }
    int k = 1;
    while (k <= s) {
        zeroOnePack(k * v, k * w);
        s -= k;
        k <<= 1;
    }
    if (s > 0) zeroOnePack(s * v, s * w);
}

int main(void) {
    scanf("%d%d", &n, &V);
    while (n--) {
        scanf("%d%d%d", &v, &w, &s);
        multiPack(v, w, s);
    }
    printf("%d\n", f[V]);
    return 0;
}

感谢阅读…

参考借鉴

思路借鉴：https://www.acwing.com/solution/content/6500/

题目出处：https://www.acwing.com/problem/content/6/

代码出处：http://www.acwing.com/solution/content/5672/