ZeroOneKnapsack [零一背包]
# 介绍
# 背包问题
背包问题（Knapsack problem）是一种组合优化的 NP 完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中，背包的空间有限，但我们需要最大化背包内所装物品的价值。背包问题通常出现在资源分配中，决策者必须分别从一组不可分割的项目或任务中进行选择，而这些项目又有时间或预算的限制。
NPC 问题是没有多项式时间复杂度的解法的，但是利用动态规划，我们可以以伪多项式时间复杂度求解背包问题。一般来讲，背包问题有以下几种分类：
- 01 背包问题
- 完全背包问题
- 多重背包问题
# 零一背包
原理：
状态转换方程： dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + c[i])
如果装不下当前物品，那么前 n 个物品的最佳组合和前 n-1 个物品的最佳组合是一样的。
如果装得下当前物品。选取假设 1 和假设 2 中较大的价值，为当前最佳组合的价值。
- 假设 1：装当前物品，在给当前物品预留了相应空间的情况下，前 - 1 个物品的最佳组合加上当前物品的价值就是总价值。
- 假设 2：不装当前物品，那么前 n 个物品的最佳组合和前 n-1 个物品的最佳组合是一样的。
背包的回溯：
从表的右下角开始回溯，如果发现前 n 个物品最佳组合的价值和前 n-1 个物品最佳组合的价值一样，说明第 n 个物品没有被装入。否则，第 n 个物品被装入。
# 实现
# JavaScript
/**
* A Dynamic Programming based solution for calculating Zero One Knapsack
* https://en.wikipedia.org/wiki/Knapsack_problem
*/
const zeroOneKnapsack = (arr, n, cap, cache) => {
if (cap === 0 || n === 0) return cache[n][cap] = 0
if (cache[n][cap] !== -1) return cache[n][cap]
if (arr[n - 1][0] <= cap) return cache[n][cap] = Math.max(arr[n - 1][1] + zeroOneKnapsack(arr, n - 1, cap - arr[n - 1][0], cache), zeroOneKnapsack(arr, n - 1, cap, cache))
return cache[n][cap] = zeroOneKnapsack(arr, n - 1, cap, cache)
}
const example = () => {
/*
Problem Statement:
You are a thief carrying a single bag with limited capacity S. The museum you stole had N artifact that you could steal. Unfortunately you might not be able to steal all the artifact because of your limited bag capacity.
You have to cherry pick the artifact in order to maximize the total value of the artifacts you stole.
Link for the Problem: https://www.hackerrank.com/contests/srin-aadc03/challenges/classic-01-knapsack
*/
let input = `1
4 5
1 8
2 4
3 0
2 5
2 3`
input = input.trim().split('\n')
input.shift()
const length = input.length
const output = []
let i = 0
while (i < length) {
const cap = Number(input[i].trim().split(' ')[0])
const currlen = Number(input[i].trim().split(' ')[1])
let j = i + 1
const arr = []
while (j <= i + currlen) {
arr.push(input[j])
j++
}
const newArr = arr.map(e =>
e.trim().split(' ').map(Number)
)
const cache = []
for (let i = 0; i <= currlen; i++) {
const temp = []
for (let j = 0; j <= cap; j++) {
temp.push(-1)
}
cache.push(temp)
}
const result = zeroOneKnapsack(newArr, currlen, cap, cache)
output.push(result)
i += currlen + 1
}
return output
}
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
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
# 扩展
完全背包：每个物品可以无限制的取。 多重背包：每个物品可以取给定次数。多重背包问题可以转换为零一背包问题，将重复的物品看做不同的物品即可。
背包问题详解参见：
完全背包状态转换方程： dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + c[i])
# 参考
编辑 (opens new window)
上次更新: 2022/10/27, 22:22:22