多重背包单调队列优化思路_单调队列优化多重背包

算法

应该是个经典算法&＃xff0c;稍微记录一下

用\(w[i]\)表示重量&＃xff0c;\(v[i]\)表示价值

那么不难写出转移方程

\(f[i][j] &＃61; max(f[i - 1][j - k * w[i]] &＃43; k * v[i])\)

考虑用单调队列优化。

我们若要用单调队列优化&＃xff0c;那么必须满足转移时所需要的状态只与\(k\)有关

这里要用到一个神仙操作&＃xff0c;对\(j \% w[i]\)分类

因为对于\(\% j\)后相同的数&＃xff0c;转移时只有\(k\)的值不相同。

设\(a &＃61; \frac{j}{w[i]}, b &＃61; j \% w[i]\)

那么转移方程可以写成

\(f[i][j] &＃61; max(f[i - 1][b &＃43; k * w[i]] - k * v[i]]) &＃43; a * v[i]\)

对每个\(j \% w[i]\)分别维护单调队列即可。。

同时\(f\)数组可以滚动一下

代码

#include

#define LL long long

using namespace std;

const int MAXN &＃61; 1001;

inline int read() {

int x &＃61; 0, f &＃61; 1; char c &＃61; getchar();

while(c <&＃39;0&＃39; || c > &＃39;9&＃39;) {if(c &＃61;&＃61; &＃39;-&＃39;) f &＃61; -1; c &＃61; getchar();}

while(c >&＃61; &＃39;0&＃39; && c <&＃61; &＃39;9&＃39;) x &＃61; x * 10 &＃43; c - &＃39;0&＃39;, c &＃61; getchar();

return x * f;

}

int N, M, C, q[10001];

LL f[10001], val[10001];

main() {

N &＃61; read(); M &＃61; read(); C &＃61; read();

for(int i &＃61; 1; i<&＃61; N; i&＃43;&＃43;) {

int w &＃61; read(), v &＃61; read(), d &＃61; read();

for(int b &＃61; 0; b

for(int k &＃61; 0, h &＃61; 1, t &＃61; 0, j &＃61; b; j <&＃61; C; k&＃43;&＃43;, j &＃43;&＃61; w) {

int a &＃61; k * v, tmp &＃61; f[j] - a;// a &＃61; j / w * v &＃61; k * v

while(h <&＃61; t && tmp > val[q[t]]) t--;

q[&＃43;&＃43;t] &＃61; k; val[q[t]] &＃61; tmp;//由于这里的val需要被更新过后才能使用&＃xff0c;因此不用清空

while(h <&＃61; t && q[h] &＃43; d

f[j] &＃61; val[q[h]] &＃43; a;

}

}

}

for(int i &＃61; 1; i <&＃61; M; i&＃43;&＃43;) {

int a &＃61; read(), b &＃61; read(), c &＃61; read();//

for(int j &＃61; C; j >&＃61; 0; j--)//枚举一下体积

for(int k &＃61; 0; k <&＃61; j; k&＃43;&＃43;)

f[j] &＃61; max(f[j], f[j - k] &＃43; (a * k &＃43; b) * k &＃43; c);

}

cout <

return 0;

}