01背包

出自《背包九讲》

问题

有$N$个物品和一个容量为$V$的背包。放入第$i$件物品体积是$c_i$,得到价值$w_i$。

求解将那些物品装入背包可使得价值总和最大。

思想

$dp[i][j]$: 表示前$i$件物品中选若干件,放入容量为$j$的背包中,可获得的最大价值。

考虑第i件物品放或不放,那么转移就是:

$$dp[i][j] = Max(dp[i-1][j], dp[i-1][j-c_i] + w_i)$$

优化1

因为我们发现当前状态只和上一个状态相关,因此第一维实际上只要存2个数即可。

优化2

我们通过转移的顺序发现,如果我们倒过来进行转移,只需要一维即可。

初始化问题

如果是恰好装满, 那么$dp[0][i]$都要初始化为0, 而其他都要初始化为负无穷。

如果是不必装满,那么$dp[0][i]$要初始化为0, 转移的时候改一改即可。

变形

容量和价值换一换,$dp[i][j]$:表示前i件物品,价值为j的最小容量。

一样做。

可达性背包

问$N$个物品,容量为$V$的背包,可以组成的价值的种类数。

需要用$bitset$优化。

$bitset$ 中的每一位表示这个价值是否能达到。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bitset<maxn> bt[2][maxn];

for (int j = 0; j <= V; j++) {
bt[0][j].reset();
bt[1][j].reset();
}
for (int i = 1; i <= N; i++) {
int id = i & 1;
for (int j = 0; j <= V; j++) {
if (j < c[i])
bt[id][j] = bt[id ^ 1][j];
else
bt[id][j] |= bt[id ^ 1][j - c[i]].set(w[i]);
}
}
cout << bt[N & 1][V].count() << endl;

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// 恰好装满
clr(dp,0xc0); // 初始化负无穷
clr(dp[0],0);
for (int i = 1; i <= N; i++) {
for (int j = c[i]; j <= V; j++) {
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - c[i]] + w[i]);
}
}
// 不必装满
clr(dp[0], 0);
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= V; j++) {
if (j < c[i])
dp[i][j] = dp[i - 1][j];
else
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - c[i]] + w[i]);
}
}

// 优化1
clr(dp[0], 0);
for (int i = 1; i <= N; i++) {
int id = i & 1;
for (int j = 0; j <= V; j++) {
if (j < c[i])
dp[id][j] = dp[id ^ 1][j];
else
dp[id][j] = max(dp[id ^ 1][j], dp[id ^ 1][j - c[i]] + w[i]);
}
}
cout << dp[N & 1][V] << endl;

// 优化2
clr(dp, 0);
for (int i = 1; i <= N; i++) {
for (int j = V; j >= c[i]; j++) {
dp[j] = max(dp[j], dp[j - c[i]] + w[i]);
}
}
cout << dp[V] << endl;

从n中类型的东西挑m个(可选同种) (组合数学)

1
2
3
4
5
6
7
8
9
for(int i=1;i<=n;i++){
dp[i][1] = i;
dp[0][i] = 0;
}
for(int i=1;i<=n;i++){
for(int k=2;k<=m;k++){
dp[i][k] = dp[i-1][k] + dp[i][k-1];
}
}
Thank you for your support!