背包¶

# 套路 & 经验积累 DP - chenhongxuan的小破站 - 洛谷博客

01背包¶

塞满证明：01背包装满问题（dp）_01 物品是否能将背包装满呢-CSDN博客

关于初始化的一些小技巧：
使用一维数组：

1. 如果题目没有要求恰好把背包装满，那么很简单，dp数组全部初始化为0即可。
2. 如果题目要求恰好把背包装满，且求的的是价值的最大值，那么dp数组全部初始化为-INF，仅仅把dp[0]置为0。
3. 如果题目要求恰好把背包装满，但是求的是价值的最小值，那么dp数组全部初始化为INF，仅仅把dp[0]置为0。
4. 恰好塞满求方案，则只将dp[0]置为1。

多重背包——二进制分组优化¶

原理¶

如果p=1000
朴素的算法需要遍历1000多次

等价转换：我们知道二进制可以表示出所有正整数
将数量拆解，从1开始，尽可能多的二进制数
这样就能用这些新数字重新表示1~1000的所有数字
而不必一个一个遍历

但不等同于类似于快速幂的迭代求解
这类问题是分解原数字
即拆成尽可能少的二进制数字来简便运算

实现¶

倍增k 将1000个依次递减 比如：
1000 = 1、2、4、8、16、32、64、128、256、489

1
2
3
4
5
6
7
8
9

int k=1;
while(k<p[i]){
    // for in capa:: DP k;
    p[i]-=k;
    k<<=1;
}
// 偷懒：直接copy上面的dp方程即可
k=p[i];
// for in capa:: DP k(489);

（直接在dp时进行）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

int num[maxn][2], dp[maxn];
int N, V, c, w, n, t;
cin >> V >> N;
for(int i = 1; i <= N; ++i)
{
    cin >> c >> w >> n;
    for(int k = 1; k < n; k<<=1)
    {
        for(int j = V; j >= k*c; --j)
            dp[j] = max(dp[j], dp[j-k*c]+k*w);
            // 该“物品”的花费：k*cost[i] 收益：k*value[i]
        n -= k;
    }
    for(int j = V; j >= n*c; --j)
        dp[j] = max(dp[j], dp[j-n*c]+n*w);
}

多重背包——单调队列优化¶

【动态规划/背包问题】多重背包の单调队列优化 - 知乎 (zhihu.com)

dd大牛的《背包九讲》

分组背包（泛化背包）¶

P7381 [COCI2018-2019#6] Sličice - 洛谷 | 计算机科学教育新生态

一个物品的价值随着你分配给它的费用而变化；约等于一个组只能选其中一个物品（为什么不是等价？想想看）一个组内可能有费用相同而价值不同的物品

先枚举组（物品），再枚举容量，最后是组内物品（或：物品在不同费用下的价值）。这样就确保了每个容量仅通过了一个组内的物品进行转移，因此还需要逆序（用0-1的代码）。

类比一下其他的背包：先枚举物品，再枚举容量，第三维组内只有一个物品。

也就是说设 \(f[k][v]\) 表示前k组物品花费费用v能取得的最大价值，则有：

1
2
3
4

for k in 所有的组
    for v=V..0
        for i in 组k
            f[v]=max{f[v],f[v-c[i]]+w[i];

树上依赖背包¶

方案总数¶