-
Notifications
You must be signed in to change notification settings - Fork 1
/
complete-knapsack.ts
83 lines (74 loc) · 3.2 KB
/
complete-knapsack.ts
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
/**
* 完全背包问题
* 有 N 件物品和一个容量为 V 的背包。第 i 件物品的体积是 vi,价值是 wi。
* 求:将哪些物品装入背包可使这些物品在不超过背包容量 V 的前提下价值总和最大。
* 和 0/1 背包问题不同的是,此处每种物品都可以用 0 个或者无数个。
*
* 求解思路:
* 和 0/1 背包的思路类似(请先参见 0/1 背包问题的说明)。
* 我们用 dp[i][j] 表示在可用空间为 j 的情况下,利用前 i 个物品可以构成的最大价值。
* 注意:每个物品可以用 0 次或者多次。
* 分两种情况:
* 1. 用第 i 个物品。此时剩余空间为 j - vi。注意,接下来要考察的问题和 0/1 背包有所不同,在 0/1 背包中,用了 i 物品后,
* 只剩下 i - 1 个物品可用了,但此处因为不限物品使用次数,则剩下可用的物品还是 i 个,所以此时
* dp[i][j] = dp[i][j - vi] + wi。
* 注意 dp[i][j - vi] 的含义:它表示在剩余空间 j - vi 的情况下,前 i 个物品能够组成的最大价值,这里面就包含了用 0 个
* 或者多个物品 i 的情况。
* (需仔细理解情况 1,它囊括了在剩余空间 j 下用 1 个或多个物品 i 的所有场景,只有理解了这点,才能理解情况 2 中只需要考虑前 i - 1 个物品。)
* 2. 除了 情况 1 以外,还有一种情况需要考虑:完全不用物品 i,此时剩余空间还是 j,也就是考察用前 i - 1 个物品在 j 空间构成
* 的最大价值。
*(情况 1 考察用(1 个或者多个)物品 i 的场景;情况 2 考察不用物品 i 的场景;)
* 最终取两种情况中价值最大的。
*
* 转换方程:
* 当 j < vi 时:
* dp[i][j] = dp[i - 1][j]
* 否则:
* dp[i][j] = max(dp[i - 1][j], dp[i][j - vi] + wi)
* 从转换方程看,和 0/1 背包唯一的区别就是将 dp[i - 1][j - vi] + wi 改成了 dp[i][j - vi] + wi。
*
* 优化:
* 和 0/1 背包一样,可以通过滚动数组将空间复杂度优化到 O(V)。略。
*/
interface Goods {
// 物品价值
w: number;
// 物品体积,正整数
v: number;
}
/**
* 背包问题
* @param goods - 物品集合
* @param V - 背包容量。整数
* @returns 最大价值
*/
function knapsack(goods: Goods[], V: number): number {
if (!goods.length || !V) {
return 0
}
const N = goods.length
// 二维动态规划表,大小:N+1 * V+1
const dp: number[][] = []
// 初始化
for (let i = 0; i <= N; i++) {
dp[i] = []
dp[i][0] = 0
}
for (let j = 0; j <= V; j++) {
dp[0][j] = 0
}
for (let i = 1; i <= N; i++) {
for (let j = 1; j <= V; j++) {
// 注意:i 表示前 i 个物品,转成下标需要减 1
if (goods[i - 1].v > j) {
// 当前物品体积大于可用体积,无法用当前物品
dp[i][j] = dp[i - 1][j]
} else {
// 可用该物品,用 0 个或多个,取最大的
dp[i][j] = Math.max(goods[i - 1].w + dp[i][j - goods[i - 1].v], dp[i - 1][j])
}
}
}
return dp[N][V]
}
export { knapsack, Goods }