01背包
有$n$个重量和价值分别为$w_{i}$, $v_{i}$的物品。从这些物品中挑选出总重量不超过$W$的物品，求所有挑选方案中价值总和的最大值
$1 \leq n \leq 100$
$1 \leq w_{i}, v_{i} \leq 100$
$1 \leq W \leq 10000$
$dp[i+1][j] := $ 从前$i$个物品中挑选出总重量不超过$j$的物品，所有挑选方案中价值总和的最大值.
$dp[i+1][j] = max(dp[i][j], dp[i][j-w[i]] + v[i])$
1
2
3
4
5
6
7
8
9
10
11
12
| void solve(){
for(int i = 0; i < n; i++)
for(int j = 0; j <= W; j++){
if(j - w[i] >= 0) {
dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]], + v[i]);
}
else {
dp[i + 1][j] = d[i][j];
}
}
printf("%d\n", dp[n][W]);
}
|
$dp[i][j] :=$ 从第$i$个物品开始，挑选出总重量不超过$j$的物品，所有挑选方案中价值总和的最大值.
$dp[i][j] = max(dp[i+1][j], dp[i+1][j-w[i]] + v[i])$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| dp[MAX_N+1][MAX_W+1];
int N;
int solve(int i, int j){
int res;
if (dp[i][j] >= 0){
return dp[i][j];
}
if (i == n) {
res = 0;
}
if (j < w[i]) {
res = solve(i + 1, j);
}
else{
res = max(solve(i + 1, j), solve(i + 1, j - w[i]) + v[i]);
}
return dp[i][j] = res;
}
void main() {
memset(dp, -1, sizeof(dp));
printf("%d\n", solve(0, W));
}
|
1
2
3
4
5
6
7
| for (int i = n - 1; i >=0; i--)
for(int j = 0; j <= W; j++) {
if(j - w[i] < 0)
dp[i][j] = dp[i + 1][j];
else
dp[i][j] = max(dp[i + 1][j], dp[i + 1][j - w[i]] + v[i]);
}
|
此外，还可以把状态转移想象成从“前$i$个物品中选取总重量不超过$j$时的状态 ”向“前$i+1$个物品中选取总重量不超过$j$” 和“前$i + 1$个物品中选取总重量不超过$j + w[i]$时的状态”的转移
1
2
3
4
5
6
7
8
9
| void solve() {
for (int i = 0; i < n; i++)
for (int j = 0; j <= W; j++) {
dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
if (j + w[i] <= W) {
dp[i + 1][j + w[i]] = max(dp[i + 1][j + w[i]], dp[i][j] + v[i]);
}
}
}
|
最长公共子序列问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| int n, m;
int dp[NAX_N][MAX_M];
char s[MAX_N], t[MAX_M];
void solve() {
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(s[i] == s[j])
dp[i + 1][j + 1] = dp[i][j] + 1;
else
dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]);
}
}
printf("%d\n", dp[n][m]);
}
|
完全背包问题
$dp[i+1][j]:=$从前i+1个物品中挑选总重量不超过j时总价值的最大值。
$dp[0][j]=0$
$dp[i+1][j]=max(dp[i][j-kw[i]]+kv[i]) \ \ |\ (0 \leq k )$
1
2
3
4
5
6
7
8
9
10
11
12
| int dp[MAX_N][MAX_M];
void solve() {
for(int i = 0; i < n; i++) {
for (int j = 0; j <= W; j++) {
for (int k = 0; k * w[i] <= j; k++) {
dp[i + 1][j] = max(dp[i][j], dp[i][j - k * w[i]] + k * v[i]);
}
}
}
printf("%d\n", dp[n][W]);
}
|
在$dp[i+1][j]$中选择$k(k\ \geq\ 1)$个的情况，与在$dp[i + 1][j - w[i]]$中选择k-1个的情况是相同的，所以$dp[i+1][j]$的递推种$k \geq 1$的部分已经在$dp[i+1][j-w[i]]$种计算完成了。
$dp[i+1][j]=max(dp[i][j-kw[i]]+kv[i]) \ \ |\ (0 \leq k )$
$=max(dp[i][j], max(dp[i][j-kw[i]]+kv[i]) \ \ |\ (1 \leq k ))$
$=max(dp[i][j], max(dp[i][(j-w[i])-kw[i]]+kv[i]\ \ |\ (0 \leq k ))+v[i] )$
$=max(dp[i][j], dp[i+1][j-w[i]]+v[i])$