01背包单调队列优化代码
时间: 2023-05-14 07:06:54 浏览: 66
以下是01背包单调队列优化的代码:
```c++
#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;
}
```
希望能够帮到你!
相关问题
单调队列优化多重背包代码
下面是单调队列优化多重背包的代码实现:
```c++
#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 表示背包的容量。
单调队列优化多重背包的代码
以下是单调队列优化多重背包的代码示例:
```cpp
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 100010;
int n, m;
int w[maxn], v[maxn];
int dp[maxn];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> w[i] >> v[i];
}
for (int i = 1; i <= n; i++) {
for (int j = w[i]; j <= m; j++) {
deque<int> q;
for (int k = 0; k * w[i] <= j; k++) {
int x = dp[j - k * w[i]] - k * v[i];
while (!q.empty() && x >= q.back()) q.pop_back();
q.push_back(x);
dp[j] = q.front() + k * v[i];
if (k - q.front() >= w[i]) q.pop_front();
}
}
}
cout << dp[m] << endl;
return 0;
}
```
解析:
这个代码是单调队列优化的多重背包的实现代码。首先读入数据,然后对于每个物品,对于每个容量 $j$,我们都要重新开一个单调队列,然后对于每个物品,我们枚举这个物品选了多少个,然后把每个状态都插入到单调队列中,然后取出队头更新答案即可。
这个代码的时间复杂度为 $O(nm\log w)$,其中 $w$ 是物品的数量。因为每个物品最多选 $w$ 个,所以单调队列最多有 $O(w)$ 个元素,所以单次操作的时间复杂度为 $O(\log w)$。总共有 $nm$ 个状态需要更新,所以总时间复杂度为 $O(nm\log w)$。