01背包单调队列优化代码

以下是01背包单调队列优化的代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,w[N],v[N],f[N];
deque<int> q;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d%d",&w[i],&v[i]);
    for(int i=1;i<=n;i++){
        while(q.size()&&q.front()<i-m) q.pop_front();
        if(q.size()) f[i]=f[q.front()]+v[i];
        while(q.size()&&f[q.back()]>f[i]) q.pop_back();
        q.push_back(i);
    }
    int ans=0;
    for(int i=1;i<=n;i++) ans=max(ans,f[i]);
    printf("%d\n",ans);
    return 0;
}

希望能够帮到你！

相关问题

请给我说明01背包单调队列优化的原理，并附上代码及其注释

C知道：

01背包问题是一个经典的动态规划问题，它的解法有很多种，其中一种比较高效的解法是单调队列优化。单调队列优化的原理是通过维护一个单调递减的队列来减少状态转移的次数，从而提高算法的效率。

具体实现方法是，对于每个物品i，维护一个队列q，其中q[j]表示当背包容量为j时，前i个物品的最大价值。初始时，q[0]=0，其它位置为负无穷大。然后对于每个物品i，从大到小枚举背包容量j，将q[j-w[i]]+v[i]与q[j]比较，如果前者更大，则将q[j]更新为前者。这样，每个物品只需要枚举一次背包容量，而不是像普通的01背包算法那样需要枚举所有的状态转移。

下面是单调队列优化的01背包算法的代码及其注释：

const int N = 1005;
int n, m, w[N], v[N], q[N], f[N];

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d%d", &w[i], &v[i]);
    memset(f, -0x3f, sizeof(f)); // 初始化为负无穷大
    f[0] = 0; // 背包容量为0时，价值为0
    for (int i = 1; i <= n; i++) {
        int hh = 0, tt = -1; // 维护单调队列
        for (int j = 0; j <= m; j++) {
            if (hh <= tt && j - w[i] > q[hh]) hh++; // 队首元素已经不在当前物品的背包容量范围内，弹出队首元素
            if (hh <= tt) f[j] = max(f[j], f[q[hh]] + (j - q[hh]) * v[i]); // 更新f[j]
            while (hh <= tt && f[q[tt]] - (q[tt] - j) * v[i] <= f[j]) tt--; // 维护单调队列
            q[++tt] = j; // 将j加入队列
        }
    }
    printf("%d\n", f[m]); // 输出背包容量为m时的最大价值
    return 0;
}

注意：这里的代码是C++代码，如果您需要使用Lua语言实现，需要进行相应的语法转换。

单调队列优化多重背包代码

下面是单调队列优化多重背包的代码实现：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 10010;
int f[N];
int q[N], v[N], w[N];
int n, m;

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
    for (int i = 1; i <= n; i ++ )
        for (int j = m; j >= v[i]; j -- )
        {
            int hh = 0, tt = -1;
            for (int k = 0; k * v[i] <= j; k ++ )
            {
                int t = f[j - k * v[i]] - k * w[i];
                while (hh <= tt && q[tt] < t) tt -- ;
                q[ ++ tt] = t;
                if (hh <= tt) f[j] = max(f[j], q[hh] + k * w[i]);
            }
        }
    cout << f[m] << endl;
    return 0;
}

该代码中的单调队列使用了双端队列来实现，队头表示队列中最大的元素，队尾表示队列中最小的元素。当加入一个新的元素时，将队列中所有小于该元素的元素弹出，然后将该元素压入队尾。同时，如果队头元素已经超出了当前的背包容量，需要将队头元素弹出。

在遍历所有物品和背包容量的组合时，每次需要清空队列。对于每个物品，从当前背包容量到该物品体积之间的所有容量，都需要计算出最大的价值。在计算价值时，需要使用单调队列进行优化。

该算法的时间复杂度为 O(N*V)，空间复杂度为 O(V)，其中 N 表示物品的数量，V 表示背包的容量。