背包问题(01背包、完全背包、多重背包)

Contents
  1. 1. Ⅰ. 背包问题认知
  2. 2. Ⅱ. 状态与初始化
    1. 2.1. 状态
    2. 2.2. 初始化
  3. 3. Ⅲ. 01背包
  4. 4. Ⅳ. 完全背包
  5. 5. Ⅴ. 多重背包
  6. 6. Ⅵ. 多重背包の优化
    1. 6.1. 二进制优化
    2. 6.2. 单调队列优化

Ⅰ. 背包问题认知

  • $物品:不可拆分,具有三种属性(体积w_i, 价值v_i, 个数c_i)$
  • $背包问题:将物品装入V大小的背包获得最优价值的问题$
  • $c_i=1时,称为01背包$
  • $c_i=\infty 时,称为完全背包$
  • $c_i=不定值时,称为多重背包$

Ⅱ. 状态与初始化

状态

  • $f[i][j]:前i件物品装入容量为j的背包所获得的最大价值$
  • $不放第i件物品: f[i-1][j]:= 前i-1件物品装入容量为j的背包$
  • $放入1件第i件物品: f[i-1][j-w_i]:= 前i-1件物品装入容量为j-w_i的背包$

初始化

  1. $如果不要正好装满: f[0][0\sim V] = 0$
  2. $如果需要正好装满: f[0][0] = 0,f[0][1\sim V] = -INF$
  3. $初始化dp数组就是初始化f[0][x]:= “0件物品的合法状态”$
    • $对于1,此时所有容量即f[0][x]都有合法的解0,即“什么都不装”$
    • $对于2,此时只有f[0][0]有合法解且解为0,其他属于非法状态,应赋值为-INF$

Ⅲ. 01背包

1
2
3
4
5
6
7
8
9
10
11
12
//O(NV)
f[0][0 ~ V] = 0;
for(int i = 1; i <= n; ++i)
for(int j = 0; j <= V; ++j)
if(j < w[i]) f[i][j] = f[i - 1][j];
else f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + v[i]);
//O(NV) 滚动数组
f[0 ~ V] = 0;
for(int i = 1; i <= n; ++i)
for(int j = V; j >= w[i]; --j)
f[j] = max(f[j], f[j - w[i]] + v[i]);

Ⅳ. 完全背包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//O(NVK)
f[0][0 ~ V] = 0;
for(int i = 1; i <= n; ++i)
for(int j = 0; j <= V; ++j)
for(int k = 0; k * w[i] <= j; ++k)
f[i][j] = max(f[i][j], f[i - 1][j - k * w[i]] + k * v[i]);
//O(NV)
f[0][0 ~ V] = 0;
for(int i = 1; i <= n; ++i)
for(int j = 0; j <= V; ++j)
if(j < w[i]) f[i][j] = f[i - 1][j];
else f[i][j] = max(f[i - 1][j], f[i][j - w[i]] + v[i]);
//O(NV) 滚动数组
f[0 ~ V] = 0;
for(int i = 1; i <= n; ++i)
for(int j = w[i]; j <= V; ++j)
f[j] = max(f[j], f[j - w[i]] + v[i]);

Ⅴ. 多重背包

1
2
3
4
5
6
7
8
9
10
11
12
13
//O(NVK)
f[0][0 ~ V] = 0;
for(int i = 1; i <= n; ++i)
for(int j = 0; j <= V; ++j)
for(int k = 0; k <= c[i] && k * w[i] <= j; ++k)
f[i][j] = max(f[i][j], f[i - 1][j - k * w[i]] + k * v[i]);
//O(NVK)
f[0 ~ V] = 0;
for(int i = 1; i <= n; ++i)
for(int j = V; j >= 0; --j)
for(int k = 1; k <= c[i] && k * w[i] <= j; ++k)
f[j] = max(f[j], f[j - k * w[i]] + k * v[i]);

Ⅵ. 多重背包の优化

二进制优化

  • $c_i=1+2+4+\cdots+2^k+a, 0\le a < 2^{k+1}$
  • $1, 2, 4, \cdots, 2^k可以表示0\sim 2^{k+1}-1的整数,基于二进制表示$
  • $再由a即可得到0\sim c_i的所有整数了$
  • $这样物品个数由c_i个变为logc_i个,时间复杂度即为O(NVlogK)$
1
2
3
4
5
6
7
8
9
10
11
12
//O(NVlogK)
f[0 ~ V] = 0;
for(int i = 1; i <= n; ++i){
int num = c[i];
for(int k = 1; num > 0; k <<= 1){
int mul = min(k, num);
for(int j = V; mul * w[i] <= j; --j){
f[i] = max(f[j], f[j - mul * w[i]] + mul * v[i])
}
num -= mul;
}
}

单调队列优化

  • $先看O(NVK)的转移方程:f[i][j] = max\{f[i-1][j-k\times w_i]+k\times v_i\}, k\in [0, c_i]$
  • $首先j\%w_i不同的状态间是独立的,即f[i][p\times w_i+r]肯定是由f[i-1][q\times w_i + r]转移过来的$
  • $我们来推一推,令j=p\times w_i +r$
  • $f[i][j] = max\{f[i-1][j-k\times w_i]+k\times v_i\}, k\in [0, c_i]$
    $f[i][p\times w_i +r] = max\{f[i-1][(p-k)\times w_i + r]+k\times v_i\}, k\in [0, c_i]$
    $令q=p-k,得:$
    $f[i][p\times w_i +r] = max\{f[i-1][q\times w_i + r]+(p-q)\times v_i\}, q\in [p-c_i, p]$
    $按照w_i分类后p是定值,得:$
    $f[i][p\times w_i +r] = max\{f[i-1][q\times w_i + r]-q\times v_i\}+p\times v_i, q\in [p-c_i, p]$
    $令f(x)=x\times w_i + r,得:$
    $f(p)=max\{f(q)-q\times v_i\}+p\times v_i, q\in [p-c_i, p]$
  • $这个就是我们熟悉的窗口大小为c_i的单调队列优化的式子辣$
  • $单调队列优化搞一波,时间复杂度即为O(NV)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//O(NV)
int Q[V], f[2][V]; //单调队列,滚动数组
int z = 0;
memset(f[z], 0, sizeof f[z]);
f[z][0] = 0;
for(int i = 1; i <= n; ++i) {
memset(f[!z], 0, sizeof f[!z]);
for(int r = 0; r < w[i]; ++r) {
int L = 0, R = 0;
for(int p = 0; p * w[i] + r <= V; ++p) {
while(L < R && f[z][Q[R - 1] * w[i] + r] - Q[R - 1] * v[i]
<= f[z][p * w[i] + r] - p * v[i]) --R;
Q[R++] = p;
while(L < R && p - c[i] > Q[L]) ++L;
int q = Q[L];
f[!z][p * w[i] + r] = (f[z][q * w[i] + r] - q * v[i]) + p * v[i];
}
}
z = !z;
}

1. 除非注明,本博文即为原创,转载请注明链接地址
2. 本博文只代表博主当时的观点或结论,请不要恶意攻击
3. 如果本文帮到了您,不妨点一下 下面分享到 按钮,让更多的人看到