0-1背包问题（4种方法）

动态规划算法

算法思想

  1. 创建一个二维数组 dp，其中 dp[i][j] 表示考虑前 i 个物品，容量为 j 的背包所能达到的最大总价值。
  2. 初始化 dp 为全零，表示未考虑任何物品时的情况。
  3. 使用两层循环，外层循环遍历物品（从第一个物品到第 numsOfObject 个物品），内层循环遍历背包容量（从1到 capacityOfKnapsack）。
  4. 对于每个物品，如果当前背包容量 j 小于物品的重量 weight[i - 1]，则不能放入当前物品，继承上一层的最优解，即 dp[i][j] = dp[i - 1][j]。
  5. 如果当前背包容量 j 大于或等于物品的重量 weight[i - 1]，则可以选择放入或不放入当前物品，需要取两者中的较大值。
    • 如果放入当前物品，总价值为 value[i - 1] 加上剩余容量 j - weight[i - 1] 的最优解 dp[i - 1][j - weight[i - 1]]。
    • 如果不放入当前物品，总价值为上一层的最优解 dp[i - 1][j]。
    • 因此，取这两者中的较大值更新 dp[i][j]，即 dp[i][j] = max(value[i - 1] + dp[i - 1][j - weight[i - 1]], dp[i - 1][j])。
  6. 最终，dp[numsOfObject][capacityOfKnapsack] 存储了问题的最优解，即背包容量为 capacityOfKnapsack 时可以获得的最大总价值。
  7. 通过回溯过程，从 dp 数组中找出选中的物品，记录它们的索引，以构建最终的结果集。

时间复杂度： O(numsOfObject * capacityOfKnapsack)

空间复杂度： O(numsOfObject * capacityOfKnapsack)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function knapsackSolveByDP(numsOfObject, capacityOfKnapsack, weight, value):
    result = []  # 用于存储最优解的物品索引
    dp = new 2D array of size (numsOfObject + 1) x (capacityOfKnapsack + 1) initialized to 0

    for i from 1 to numsOfObject:
        for j from 1 to capacityOfKnapsack:
            if weight[i - 1] > j:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = max(value[i - 1] + dp[i - 1][j - weight[i - 1]], dp[i - 1][j])

    i = numsOfObject
    j = capacityOfKnapsack

    while i > 0 and j > 0:
        if dp[i][j] == dp[i - 1][j]:
            i = i - 1
        else:
            result.push(i - 1)  # 将当前物品的索引加入结果
            j = j - weight[i - 1]
            i = i - 1

    return result  # 返回最优解的物品索引

代码

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
vector<int> knapsackSolveByDP(int numsOfObject, int capacityOfKnapsack, vector<int> weight, vector<int> value)
{
	vector<int> result;
	vector<vector<int>> dp(numsOfObject + 1, vector<int>(capacityOfKnapsack + 1, 0));
    for (int i = 1; i <= numsOfObject; i++) {
        for (int j = 1; j <= capacityOfKnapsack; j++) {
            if (j < weight[i - 1]) {
				dp[i][j] = dp[i - 1][j];
			}
            else {
				dp[i][j] = max(value[i - 1] + dp[i - 1][j - weight[i - 1]], dp[i - 1][j]);
			}
		}
	}
	int i = numsOfObject;
	int j = capacityOfKnapsack;
    while (i > 0 && j > 0) {
        if (dp[i][j] == dp[i - 1][j]) {
			i--;
		}
        else {
			result.push_back(i - 1);
			j -= weight[i - 1];
			i--;
		}
	}
	return result;
}

贪心算法（不一定得出最优解）

算法思想

首先计算每个物品的单位重量价值，然后根据单位重量价值从高到低对物品进行排序。接着，它按顺序选择单位重量价值最高的物品放入背包，直到背包容量不足以放下更多的物品。

时间复杂度： O(numsOfObject * capacityOfKnapsack)

空间复杂度： O(numsOfObject)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function knapsackSolveByGreedy(numsOfObject, capacityOfKnapsack, weight, value):
    result = []  # 用于存储最优解的物品索引
    valuePerWeight = []  # 存储每个物品的单位重量价值和对应的物品索引

    for i from 0 to numsOfObject - 1:
        valuePerWeight.push((value[i] / weight[i], i))

    # 根据单位重量价值从高到低对物品进行排序
    sort(valuePerWeight in descending order by the first element)

    for i from 0 to numsOfObject - 1:
        index = valuePerWeight[i].second  # 取出单位重量价值最高的物品索引
        if capacityOfKnapsack >= weight[index]:
            result.push(index)  # 将当前物品的索引加入结果
            capacityOfKnapsack -= weight[index]

    return result  # 返回最优解的物品索引

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<int> knapsackSolveByGreedy(int numsOfObject, int capacityOfKnapsack, vector<int> weight, vector<int> value)
{
	vector<int> result;
	vector<pair<double, int>> valuePerWeight;
	for (int i = 0; i < numsOfObject; i++) {
		valuePerWeight.push_back(make_pair(value[i] / weight[i], i));
	}
	sort(valuePerWeight.begin(), valuePerWeight.end(), [](pair<double, int> a, pair<double, int> b) {return a.first > b.first; });
	for (int i = 0; i < numsOfObject; i++) {
		if (capacityOfKnapsack >= weight[valuePerWeight[i].second])
		{
			result.push_back(valuePerWeight[i].second);
			capacityOfKnapsack -= weight[valuePerWeight[i].second];
		}
	}
	return result;
}

回溯法

算法思想

  1. 初始化一些变量，包括 result（存储最优解的物品索引列表），temp（用于临时存储当前路径的物品索引列表），maxValue（用于记录当前已探索路径的最大价值），currentWeight（当前路径的总重量），currentValue（当前路径的总价值），以及 currentObject（当前正在考虑的物品索引）。
  2. 进入循环，只要还有未考虑的物品，就继续执行以下步骤。
  3. 检查当前物品是否可以放入背包，即检查加上当前物品后是否会超过背包的容量。如果不会超过，将当前物品放入背包，更新 currentWeight 和 currentValue，然后将当前物品的索引添加到 temp 列表中。
  4. 检查当前路径的总价值是否大于 maxValue，如果是，更新 maxValue 和将 temp 中的物品索引复制到 result 中，以记录找到的新最优解。
  5. 如果当前物品无法放入背包，或者路径已经探索完，执行回溯操作。将 temp 列表中的最后一个物品索引弹出（pop），并更新 currentObject、currentWeight 和 currentValue，以模拟不选择当前物品的情况。
  6. 循环继续，直到所有物品都被考虑过，或者没有更多可行的选择时结束。
  7. 返回 result，它包含了最佳解的物品索引列表。

时间复杂度： O(2^n)

  • 回溯算法的时间复杂度通常随着问题规模的增加呈指数增长。
  • 在该算法中，时间复杂度主要受到两个因素的影响：物品的数量（numsOfObject）和背包容量（capacityOfKnapsack）。
  • 对于每个物品，算法需要考虑两种情况：包含物品和不包含物品，因此需要进行指数级的探索。
  • 最坏情况下，算法需要探索所有可能的物品组合，因此时间复杂度为 O(2^n)。

空间复杂度： O(n)

  • 回溯算法的空间复杂度通常受到递归调用和数据结构的影响。
  • 在该算法中，主要占用空间的是递归调用的栈空间和存储结果的数据结构。
  • 递归调用的深度受到物品数量的影响，最坏情况下可能达到 numsOfObject，因此栈空间的空间复杂度为 O(n)。
  • 数据结构方面，主要占用空间的是 result、temp、maxValue、currentWeight、currentValue 和 currentObject 这些变量。
  • 因此总的空间复杂度 O(n)。
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
function knapsackSolveByBacktracking(numsOfObject, capacityOfKnapsack, weight, value):
    result = []  # 用于存储最优解的物品索引
    temp = []  # 用于暂时存储当前可能的解
    maxValue = 0  # 用于记录当前最大价值
    currentWeight = 0  # 当前所选物品的总重量
    currentValue = 0  # 当前所选物品的总价值
    currentObject = 0  # 当前正在考虑的物品索引

    while currentObject < numsOfObject:
        if currentWeight + weight[currentObject] <= capacityOfKnapsack:
            currentWeight += weight[currentObject]
            currentValue += value[currentObject]
            temp.push_back(currentObject)
            currentObject++
            if currentValue > maxValue:
                maxValue = currentValue
                result = temp
        else:
            if temp.empty():
                break
            currentObject = temp.back() + 1
            currentWeight -= weight[temp.back()]
            currentValue -= value[temp.back()]
            temp.pop_back()

    return result  # 返回最优解的物品索引

代码

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
vector<int> knapsackSolveByBacktracking(int numsOfObject, int capacityOfKnapsack, vector<int> weight, vector<int> value)
{
	vector<int> result;
	vector<int> temp;
	int maxValue = 0;
	int currentWeight = 0;
	int currentValue = 0;
	int currentObject = 0;
	while (currentObject < numsOfObject) {
		if (currentWeight + weight[currentObject] <= capacityOfKnapsack) {
			currentWeight += weight[currentObject];
			currentValue += value[currentObject];
			temp.push_back(currentObject);
			currentObject++;
			if (currentValue > maxValue) {
				maxValue = currentValue;
				result = temp;
			}
		}
		else {
			if (temp.empty()) {
				break;
			}
			currentObject = temp.back() + 1;
			currentWeight -= weight[temp.back()];
			currentValue -= value[temp.back()];
			temp.pop_back();
		}
	}
	return result;
}

分支定界

算法思想

  1. 首先，将输入的物品按照价值-重量比（value/weight）从高到低排序，以便后续选择物品时优先选择价值高的物品。
  2. 创建一个优先队列（priority_queue）pq，用于维护待处理的子问题。
  3. 初始化一个根节点 root，其中 bound 设置为通过计算函数 caculateBound 得到的上界值。根节点的 level、weight、value 和 selectedItems 初始化为0。
  4. 将根节点 root 加入优先队列 pq。
  5. 进入循环，只要队列不为空，就继续执行以下步骤。
  6. 从队列中取出优先级最高的节点 node。
  7. 检查 node 的 bound 是否大于当前已知的最大价值 maxValue。如果不是，剪枝并跳过该节点。
  8. 如果 node 的 bound 大于 maxValue，则生成两个子节点 left 和 right：
    • left 表示选择当前物品（level 层级的物品）放入背包，更新 level、weight、value 和 selectedItems，然后重新计算其 bound 值。如果放入后不超过背包容量且 bound 大于 maxValue，则更新 maxValue 并将 left 加入队列。
    • right 表示不选择当前物品，直接进入下一层级，更新 level 并重新计算其 bound 值。如果 bound 大于 maxValue，则将 right 加入队列。
  9. 重复步骤6到步骤8，直到队列为空或无法找到更高优先级的节点。
  10. 最终，根据 selectedItems 中的标记，将选中的物品加入结果集 result 中。

时间复杂度：O(2^N * N)

  • 时间复杂度主要受到算法中循环的次数和每次循环的计算复杂度的影响。
  • 在该算法中，主要的计算负担是计算上界值（calculateBound 函数的调用）和在优先队列中的节点的处理。
  • 假设有 N 个物品，算法可能会生成最多 2^N 个子问题（每个节点都有两个子节点：选择物品和不选择物品）。
  • 对于每个节点，需要计算其上界值，这通常需要遍历剩余的物品，计算总价值，因此计算上界值的复杂度为 O(N)。
  • 每个节点的处理也涉及到常数时间的操作，如更新值、加入队列等。
  • 因此，总的时间复杂度约为 O(2^N * N)。

空间复杂度：O(2^N)

  • 空间复杂度主要受到数据结构和递归调用的影响。
  • 数据结构方面，主要占用空间的是优先队列（pq）和节点对象（Node）。
  • 优先队列的空间复杂度取决于队列中的节点数量，最坏情况下可能达到 O(2^N)。
  • 节点对象的空间复杂度取决于每个节点的数据结构，其中包括整数、数组和布尔数组，总体来说，占用的空间相对较小。
  • 递归调用可能会占用一些栈空间，但根据具体情况，递归深度通常不会很大，因此占用的空间也相对较小。
  • 因此，总的空间复杂度可以粗略估计为 O(2^N)。
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
Function knapsackSolveByBranchAndBound(numsOfObject, capacityOfKnapsack, weight, value):
    // Create a priority queue to manage nodes
    pq = Priority Queue
    
    // Sort items based on value/weight ratio
    Sort items by (value / weight) in descending order
    
    // Initialize variables to track the best solution
    maxValue = 0
    selectedItems = Array of size numsOfObject
    
    // Create and initialize the root node
    root = Node(level: 0, weight: 0, value: 0, bound: calculateBound(root, items, capacityOfKnapsack))
    root.selectedItems = Array of size numsOfObject
    
    // Push the root node to the priority queue
    Push root to pq
    
    // Start processing nodes
    while pq is not empty:
        node = Pop the highest priority node from pq
        
        // Check if the bound of the node is greater than the current best value
        if node.bound > maxValue:
            // Create left and right child nodes
            left = Copy node
            right = Copy node
            
            // Process the left child node (include the item)
            left.level = node.level + 1
            left.weight += items[left.level - 1].weight
            left.value += items[left.level - 1].value
            left.selectedItems[left.level - 1] = true
            left.bound = calculateBound(left, items, capacityOfKnapsack)
            
            if left.weight <= capacityOfKnapsack and left.bound > maxValue:
                maxValue = left.value
                Copy left.selectedItems to selectedItems
            
            if left.bound > maxValue and left.level - 1 < numsOfObject:
                Push left to pq
            
            // Process the right child node (exclude the item)
            right.level = node.level + 1
            right.bound = calculateBound(right, items, capacityOfKnapsack)
            
            if right.bound > maxValue and right.level - 1 < numsOfObject:
                Push right to pq
    
    result = Empty Array
    for i from 0 to numsOfObject:
        if selectedItems[i] is true:
            Add items[i] to result
    
    Return result
End Function

代码

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
84
85
86
87
88
struct Item {
	int weight;
	int value;
	Item() : weight(0), value(0) {};
	bool operator<(const Item& item) const {
		return (double(value) / weight) < (double(item.value) / item.weight);
	}
};
struct Node {
	int level;
	int weight;
	int value;
	int bound;
	vector<bool> selectedItems;
	Node(int numsOfObject) : level(0), weight(0), value(0), bound(0) {
		selectedItems.resize(numsOfObject);
	};
	bool operator<(const Node& node) const {
		return bound < node.bound;
	}
};
int caculateBound(Node& node, vector<Item>& items, int capacityOfKnapsack) {
	if (node.weight >= capacityOfKnapsack)
		return 0;
	int bound = node.value;
	int weight = node.weight;
	int level = node.level;
	int numsOfObject = items.size();
	while (level < numsOfObject && weight + items[level].weight <= capacityOfKnapsack) {
		bound += items[level].value;
		weight += items[level].weight;
		level++;
	}
	if (level < numsOfObject) {
		bound += (capacityOfKnapsack - weight) * (double(items[level].value) / items[level].weight);
	}
	return bound;
}
vector<Item> knapsackSolveByBranchAndBound(int numsOfObject, int capacityOfKnapsack, vector<int> weight, vector<int> value)
{
	vector<bool> selected(numsOfObject);
	vector<Item> items(numsOfObject);
	for (int i = 0; i < numsOfObject; i++) {
		items[i].weight = weight[i];
		items[i].value = value[i];
	}
	sort(items.begin(), items.end());

	int maxValue = 0;

	priority_queue<Node> pq;
	Node root(numsOfObject);
	root.bound=caculateBound(root, items, capacityOfKnapsack);
	pq.push(root);

	while (!pq.empty()) {
		Node node = pq.top();
		pq.pop();
		if (node.bound > maxValue) {
			Node left = node;
			left.level += 1;
			left.weight += items[left.level - 1].weight;
			left.value += items[left.level - 1].value;
			left.selectedItems[left.level - 1] = 1;
			left.bound = caculateBound(left, items, capacityOfKnapsack);
			if (left.weight <= capacityOfKnapsack && left.bound > maxValue) {
				maxValue = left.value;
				selected = left.selectedItems;
			}
			if (left.bound > maxValue && left.level - 1 < numsOfObject) {
				pq.push(left);
			}
			Node right = node;
			right.level += 1;
			right.bound = caculateBound(right, items, capacityOfKnapsack);
			if (right.bound > maxValue && right.level - 1 < numsOfObject) {
				pq.push(right);
			}
		}
	}
	vector<Item> result;
	for (int i = 0; i < numsOfObject; i++) {
		if (selected[i]) {
			result.push_back(items[i]);
		}
	}
	return result;
}

输入

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
int main()
{
    int numsOfObject = 5;
    int capacityOfKnapsack = 10;
    vector<int> weight = { 2,2,6,5,4 };
    vector<int> value = { 6,3,5,4,6 };

    vector<int> dpResult = knapsackSolveByDP(numsOfObject, capacityOfKnapsack, weight, value);
	vector<int> greedyResult = knapsackSolveByGreedy(numsOfObject, capacityOfKnapsack, weight, value);
	vector<int> backtrackingResult = knapsackSolveByBacktracking(numsOfObject, capacityOfKnapsack, weight, value);
	vector<Item> branchAndBoundResult = knapsackSolveByBranchAndBound(numsOfObject, capacityOfKnapsack, weight, value);

	int maxValue = 0;
	cout << "DP: w,v" << endl; 
	maxValue = 0;
	for (int i = 0; i < dpResult.size(); i++) {
		cout << weight[dpResult[i]] << " " << value[dpResult[i]] << endl;
		maxValue += value[dpResult[i]];
	}
	cout << "maxValue: " << maxValue << endl;
	cout << endl;
	cout << "Greedy: w,v" << endl;
	maxValue = 0;
	for (int i = 0; i < greedyResult.size(); i++) {
		cout << weight[greedyResult[i]] << " " << value[greedyResult[i]] << endl;
		maxValue += value[greedyResult[i]];
	}
	cout << "maxValue: " << maxValue << endl;
	cout << endl;
	cout << "Backtracking: w,v" << endl;
	maxValue = 0;
	for (int i = 0; i < backtrackingResult.size(); i++) {
		cout << weight[backtrackingResult[i]] << " " << value[backtrackingResult[i]] << endl;
		maxValue += value[backtrackingResult[i]];
	}
	cout << "maxValue: " << maxValue << endl;
	cout << endl;
	cout << "BranchAndBound: w,v" << endl;
	maxValue = 0;
	for (int i = 0; i < branchAndBoundResult.size(); i++) {
		cout << branchAndBoundResult[i].weight << " " << branchAndBoundResult[i].value << endl;
		maxValue += branchAndBoundResult[i].value;
	}
	cout << "maxValue: " << maxValue << endl;
	cout << endl;

    return 0;
}

输出