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

Posted on Edited on In Views:
如何用动态规划求解背包问题（Knapsack problem）

背包问题（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)$ 。
最优方案就是比较这两种方案，哪个会更好些：
$$
m(i,W)=\max{m(i-1,W),m(i-1,W-w_i)+v_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