Ⅰ. 背包问题认知

• $物品：不可拆分，具有三种属性(体积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背包

//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]);

Ⅳ. 完全背包

//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]);

Ⅴ. 多重背包

//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)$

//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)$

//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;
}