响应式网站开发有哪些框架,济南电商网站建设,青岛哪里做网站,格子三合一交友婚恋网站模板多重背包——二进制优化/单调队列优化二进制优化单调队列优化代码都是 POJ1742 的#xff0c;注意#xff0c;那道题二进制优化会超时。
普通的多重背包式子#xff0c;物品个数限制#xff1a;c[i]c[i]c[i]#xff0c;单个物品价值 w[i]w[i]w[i]#xff0c;每个物品的体…
多重背包——二进制优化/单调队列优化二进制优化单调队列优化代码都是 POJ1742 的注意那道题二进制优化会超时。
普通的多重背包式子物品个数限制c[i]c[i]c[i]单个物品价值 w[i]w[i]w[i]每个物品的体积 v[i]v[i]v[i]
第一维是前 iii 个物品第二维是背包容量。 dp[i,j]max(dp[i][j],dp[i−1][j−k∗v[i]]k∗w[i])0≤k≤c[i]dp[i,j]\max(dp[i][j],dp[i-1][j-k*v[i]]k*w[i])\quad 0\le k\le c[i] dp[i,j]max(dp[i][j],dp[i−1][j−k∗v[i]]k∗w[i])0≤k≤c[i]
二进制优化
因为每个数都可以被表示成二进制形式。
二进制优化就是将物品的个数 c[i]c[i]c[i] 拆分成二进制形式将多个物品捆绑成 2i2^i2i 个形式。
然后通过捆绑后的多重组合能够组合出原来 0∼c[i]0\sim c[i]0∼c[i] 的所有选择。
i.e. 物品个数为 121212就拆分成 1(20)2(21)4(22)51(2^0)2(2^1)4(2^2)51(20)2(21)4(22)5因为剩下的不足捆绑就单独拎出来处理。
会发现这四个数就能组合出选择 0∼120\sim 120∼12 个物品的情况。
这就将第三维度枚举放的物品个数从 O(c[i])O(c[i])O(c[i]) 降到了 O(logc[i])O(\log c[i])O(logc[i])。
如果将所有信息看成同阶则复杂度为 O(n2logn)O(n^2\log n)O(n2logn)。
#include cstdio
#include cstring
#define maxn 105
#define maxm 100005
int f[maxm], a[maxn], c[maxn];
int n, m;int main() {while( scanf( %d %d, n, m ) ) {if( ! n and ! m ) break;for( int i 1;i n;i ) scanf( %d, a[i] );for( int i 1;i n;i ) scanf( %d, c[i] );memset( f, 0, sizeof( f ) );f[0] 1;for( int i 1;i n;i ) {int k 1;while( c[i] k ) {c[i] - k;for( int j m;j a[i] * k;j -- )f[j] | f[j - a[i] * k];k 1;}if( c[i] ) {for( int j m;j a[i] * c[i];j -- )f[j] | f[j - a[i] * c[i]];}}int ans 0;for( int i 1;i m;i ) ans f[i];printf( %d\n, ans );}return 0;
}单调队列优化
因为某种物品尽管有很多个但是体积是一样的。
每次都会占用背包的 v[i]v[i]v[i] 体积。
所以如果原来背包的容量为 jjj那么只会转移给 jv[i],jv[i]∗2,...,jv[i]∗c[i]jv[i],jv[i]*2,...,jv[i]*c[i]jv[i],jv[i]∗2,...,jv[i]∗c[i]这些容量在 %v[i]\% v[i]%v[i] 下同余。
将背包容量 jjj按照 %v[i]\% v[i]%v[i] 的余数分类考虑显然两个不同的余数是不会相互转移的。
式子化地令 aj/v[i],bj%v[i]⇒ja∗v[i]baj/v[i],bj\%v[i]\Rightarrow ja*v[i]baj/v[i],bj%v[i]⇒ja∗v[i]b
f[i][j]max{f[i−1][j−k∗v[i]]k∗w[i]}⇒f[i][j]max{f[i−1][(a−k)∗v[i]b]k∗w[i]}f[i][j] \max\Big\{f[i-1][j-k*v[i]]k*w[i]\Big\}\Rightarrow f[i][j]\max\Big\{f[i-1][(a-k)*v[i]b]k*w[i]\Big\}f[i][j]max{f[i−1][j−k∗v[i]]k∗w[i]}⇒f[i][j]max{f[i−1][(a−k)∗v[i]b]k∗w[i]}
k(0≤k≤c[i])k\ (0\le k\le c[i])k (0≤k≤c[i]) 反正都是枚举的变量不妨令 ka−kka-kka−k
则 f[i][j]max{f[i−1][k∗v[i]b](a−k)∗w[i]}f[i][j]\max\Big\{f[i-1][k*v[i]b](a-k)*w[i]\Big\}f[i][j]max{f[i−1][k∗v[i]b](a−k)∗w[i]}
整理得f[i][j]max{f[i−1][k∗v[i]b]−k∗w[i]}a∗w[i](a−c[i]≤k≤a)f[i][j]\max\Big\{f[i-1][k*v[i]b]-k*w[i]\Big\}a*w[i]\quad (a-c[i]\le k\le a)f[i][j]max{f[i−1][k∗v[i]b]−k∗w[i]}a∗w[i](a−c[i]≤k≤a)
换种形式表达 kkk 的范围j/v[i]−c[i]]≤k≤j/v[i]j/v[i]-c[i]]\le k\le j/v[i]j/v[i]−c[i]]≤k≤j/v[i]
是关于 jjj 的不减函数一段区间所以可以用单调队列优化。
时间复杂度是 O(nV)O(nV)O(nV)就没有 logloglog 了。
#include cstdio
#include cstring
#define maxn 100005
int n, m, head, tail;
int f[maxn], a[maxn], c[maxn], q[maxn];int main() {while( ~ scanf( %d %d, n, m ) ) {if( ! n and ! m ) break;for( int i 1;i n;i ) scanf( %d, a[i] );for( int i 1;i n;i ) scanf( %d, c[i] );memset( f, 0, sizeof( f ) ); f[0] 1;for( int i 1;i n;i ) {if( c[i] 1 ) {for( int j m;j a[i];j -- ) f[j] | f[j - a[i]];continue;}if( a[i] * c[i] m ) {for( int j a[i];j m;j ) f[j] | f[j - a[i]];continue;}for( int j 0;j a[i];j ) {head 1, tail 0;for( int k j;k m;k a[i] ) {while( head tail and q[head] k - a[i] * c[i] ) head ;if( ! f[k] ) f[k] | ( head tail );else q[ tail] k;}}}int ans 0;for( int i 1;i m;i ) ans f[i];printf( %d\n, ans );}return 0;
}
