Fork me on GitHub
0%

0-1背包问题及代码实现

背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。

相似问题经常出现在商业、组合数学,计算复杂性理论、密码学和应用数学等领域中。

也可以将背包问题描述为决定性问题,即在总重量不超过W的前提下,总价值是否能达到V。

背包问题的一个例子:应该选择哪些盒子,才能使价格尽可能地大,而保持重量小于或等于15 kg?

贪心算法

遵循贪心策略,首先尽量多地先装单位价值高的商品,如果该商品已全部拿走而背包未装满,继续尽量多地拿走每磅价值第二高的商品,依次类推,直到达到重量上限W。因此,通过将商品按每磅价值排序,贪心算法的时间运行时间是O(nlgn)。

但是这种方法并不能得到最优解:它无法保证最终能将背包装满,部分闲置的背包空间使每公斤背包空间的价值降低了

动态规划

定义子问题 $\mathbf{\text{P(i, W)}}$ 为:在前 i 个物品中挑选总重量不超过 W 的物品,每种物品至多只能挑选1个,使得总价值最大;这时的最优值记作 $m(i,W)$ ,其中 $1\leq i\leq n$ , $1\leq W\leq C$ 。

1) Optimal Substructure最优子结构:
考虑第 i 个物品,无外乎两种可能:选,或者不选。
不选的话,背包的容量不变,改变为问题 $P(i-1, W)$ ;
选的话,背包的容量变小,改变为问题 $P(i-1, W-w_i)$ 。
最优方案就是比较这两种方案,哪个会更好些:

得到:

2) Overlapping Subproblems重叠子问题

如果wi > w,$P[i, w]$转化为求解一个子问题$P[i-1, w]$;
如果wi ≤ w,$P[i, w]$转换成了求解两个子问题:
一个包含商品i,$pi + P[i-1, w- wi]$;
一个不包含商品i,$P[i-1, w]$;
两种情况中的较大者即为$P[i, w]$

很显然$P[i-1, w-wi]$与$P[i-1, w]$有重叠子问题。

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
/* A Naive recursive implementation of 0-1 Knapsack problem */
#include <iostream>
#include <algorithm>
using namespace std;

// Returns the maximum value that can be put in a knapsack of capacity W
int knapSack(int W, int wt[], int val[], int n)
{
// Base Case
if (n == 0 || W == 0)
return 0;

// If weight of the nth item is more than Knapsack capacity W, then
// this item cannot be included in the optimal solution
if (wt[n - 1] > W)
return knapSack(W, wt, val, n - 1);

// Return the maximum of two cases:
// (1) nth item included
// (2) not included
else
return max(val[n - 1] + knapSack(W - wt[n - 1], wt, val, n - 1),
knapSack(W, wt, val, n - 1));
}

// Driver program to test above function
int main()
{
int val[] = {60, 100, 120}; // 价值
int wt[] = {10, 20, 30}; // 重量
int W = 50; //背包的总capacity
int n = sizeof(val) / sizeof(val[0]);
cout << knapSack(W, wt, val, n) << endl;
return 0;
}

References:

  1. 0-1背包问题的动态规划算法
  2. 0-1 Knapsack Problem | DP-10 - GeeksforGeeks
打赏一次,年薪百万.