本笔记内容来源于算法基础课

动态规划

思路：

1. 状态表示：考虑需要几维表示状态
   1.1. 集合：状态代表了包含元素的集合
   1.2. 属性：集合的属性，如：Max, Min, 数量
2. 状态计算：集合的划分，使状态能够用更小的子集进行计算
   2.1. 划分的集合不重复，最大值，最小值不需要，但是数量必须满足
   2.2. 划分的集合不漏

优化：

对状态方程进行等价变形

注意计算方向

时间复杂度：

状态数量 $\times$ 转移的计算量

注意:

由于经常使用i-1，因此下标通常从1开始，但是注意边界的初始化

背包问题

有$N$件物品和容量为$V$的背包，对于每一个物品具有体积$v_i$和价格(权重)$w_i$

目标：在不超过容量的情况下，选取物品使得价格最大

注意：不需要装满背包

思路：

状态为$f(i, j)$, 代表所有选法的集合
满足条件：1. 只从前$i$个物品中选 2. 总体积$\leq j$

属性为所有选法的价值的最大值

因此答案为$f(N, V)$

01背包

每一件物品仅有一个，即每个物品使用0次或1次

$f(i, j)$通过是否包含$i$进行划分
不包含物品$i$的集合, 即选取范围为$1 \sim i - 1 \rightarrow $ 对应的属性(价格的最大值)为 $f(i - 1, j)$
必包含物品$i$的集合，则选取范围为$1 \sim i - 1$且体积$\leq V - v_i$再加上元素$i$ $\rightarrow$ 对应的属性(价格的最大值)为 $f(i - 1, j - v_i) + w_i$

因此最终的属性(价格的最大值)为$\max\{ f(i - 1, j), f(i - 1, j - v_i) + w_i \}$

注意：

必包含物品$i$的集合可能为空集，当$v_i > V$时

for (int i = 1; i <= n; i++)
    for (int j = 0; j <= m; j++) {
        f[i][j] = f[i - 1][j];
        if (v[i] <= j && f[i][j] < f[i - 1][j - v[i]] + w[i]) f[i][j] = f[i - 1][j - v[i]] + w[i];
    }

优化：

$f(i)$的计算只与$f(i-1)$有关，且$j, j - v_j \leq j $，因此可以使用滚动数组
由于$j-v_j \leq j$，因此化为一维后需要从大到小枚举，从而使未覆盖的值代表$i-1$层

for (int i = 1; i <= n; i++)
    for (int j = m; j >= v[i]; j--) { // 因为循环中仅有j >= v[i]才会执行，因此可以直接放到循环条件中
        if (f[j] < f[j - v[i]] + w[i]) f[j] = f[j - v[i]] + w[i];
    }

完全背包

每一件物品有无限个，即每个物品的使用次数不限

$f(i, j)$通过选取$i$的元素个数进行划分，分为$0, 1, 2, \dots , K $个，因为有容量限制，即$K = \lfloor \frac{V}{v_i} \rfloor$
不包含$k$个物品$i$的集合，，则选取范围为$1 \sim i - k$且体积$\leq V - k v_i$再加上元素$i$ $\rightarrow$ 对应的属性(价格的最大值)为 $f(i - 1, j - k v_i) + k w_i$

因此最终的属性(价格的最大值)为$\max\limits_{k=0 \sim \lfloor \frac{V}{v_i} \rfloor} \{ f(i - 1, j - kv_i) + kw_i \}$

for (int i = 1; i <= n; i++) 
    for (int j = 0; j <= m; j++) 
        for (int k = 0; k * v[i] <= j; k++) // 直至最多K个物品无法放下
            if (f[i][j] < f[i - 1][j - k * v[i]] + k * w[i]) f[i][j] = f[i - 1][j - k * v[i]] + k * w[i];

优化：

将公式展开
$f(i, j) = \max \{ f(i - 1, j), f(i - 1, j - v_i) + w_i, f(i - 1, j - 2v_i) + 2w_i , \dots , f(i - 1, j - Kv_i) + Kw_i\}$
而观察
$f(i，j - v_i) = \max \{ f(i - 1, j - v_i), f(i - 1, j - 2v_i) + w_i, f(i - 1, j - 3v_i) + 2w_i , \dots , f(i - 1, j - Kv_i) + Kw_i \}$
因此进行变形
$f(i, j) = \max \{ f(i - 1, j), f(i, j -v_i) + w_i \}$

for (int i = 1; i <= n; i++) 
    for (int j = 0; j <= m; j++) {
        f[i][j] = f[i - 1][j];
        if (v[i] <= j && f[i][j] < f[i][j - v[i]] + w[i]) f[i][j] = f[i][j - v[i]] + w[i];
    }

同样可以使用滚动数组，由于与$i$有关，因此为更新后的值，从小到大枚举即可

for (int i = 1; i <= n; i++) 
    for (int j = v[i]; j <= m; j++) {
        if (f[j] < f[j - v[i]] + w[i]) f[j] = f[j - v[i]] + w[i];
    }

多重背包

每一件物品有$s_i$个，即每个物品的使用次数至多为$s_i$

$f(i, j)$通过选取$i$的元素个数进行划分，分为$0, 1, 2, \dots , s_i $个

与完全背包类似，最终的属性(价格的最大值)为$\max\limits_{k=0 \sim s_i } \{ f(i - 1, j - kv_i) + kw_i \}$

for (int i = 1; i <= n; i++)
    for (int j = 0; j <= m; j++) 
        for (int k = 0; k <= s[i]; k++)
            if (k * v[i] <= j && f[i][j] <= f[i - 1][j - k * v[i]] + k * w[i]) f[i][j] = f[i - 1][j - k * v[i]] + k * w[i];

优化：

公式展开比较$f(i, j)$与$f(i，j - v_i)$最后一项并不相同，因此不能使用公式变形

相比于从$0 \sim s_i$逐一枚举，可以采用更高效的枚举方式$1, 2, 4, 8, \dots$即通过二进制位的组合来得到所有的枚举

对于$1, 2, 4, \dots, 2^k, C$, 可以得到$[0 , 2^{k+1} - 1] , [C , 2^{k+1} - 1 + C = S]$,从而可以得到$[0, S]$

因此可以将$S$件物品转化为$lgS$种物品，对其做01背包问题，即对每种物品取或不取，从而枚举组合

思路：

不断不断减$2^k$，直到$c = si - (1 + 2 + \dots + 2^k)$

for (int i = 1; i <=n; i++) {
    strs = re.readLine().trim().split("\\s+");
    int vi = Integer.parseInt(strs[0]);
    int wi = Integer.parseInt(strs[1]);
    int si = Integer.parseInt(strs[2]);

    int k = 1;
    while (k < si) { // 直到不能再减
        cnt++;
        v[cnt] = k * vi;
        w[cnt] = k * wi;
        si -= k; 
        k *= 2;
    }
    cnt++;
    k = si; // 得到c
    if (k > 0) {
        v[cnt] = k * vi;
        w[cnt] = k * wi;
    }
}
for (int i = 1; i <= cnt; i++)                    
    for (int j = m; j >= v[i]; j--)
            if (f[j] < f[j - v[i]] + w[i]) f[j] = f[j - v[i]] + w[i];

分组背包

物品分为若干组，每一组种只能选取一个

$f(i, j)$通过选取第$i$组物品种的元素进行划分，分为第$i$组物品种选$0$个，第$1, 2, \dots K$

最终的属性(价格的最大值)为$\max\limits_{k=1 \sim K } \{ f(i - 1, j), f(i - 1, j - v_{ik} + w_{ik} \}$

for (int i = 1; i <= n; i++)
    for (int j = 0; j <= m; j++) {
        f[i][j] = f[i - 1][j];
        for (int k = 1; k <= s[i]; k++)
            if (v[i][k] <= j && f[i][j] < f[i - 1][j - v[i][k]] + w[i][k]) f[i][j] = f[i - 1][j - v[i][k]] + w[i][k];
    }

优化：

使用滚动数组，与$i - 1$有关，因此从大到小枚举

for (int i = 1; i <= n; i++)
    for (int j = m; j >= 0; j--) {
        for (int k = 1; k <= s[i]; k++)
            if (v[i][k] <= j && f[j] < f[j - v[i][k]] + w[i][k]) f[j] = f[j - v[i][k]] + w[i][k];
    }