0-1 背包问题

发表于 更新于 分类于
动态规划

　　刷到一道背包问题，奈何不会(蠢到哭)．从网上查了解法，记一下，找了很多博客和百科还是知乎上的解法最详细明了，以下基本也就是 copy and paste 了．

　　题目描述

　　给定一组多个(n)物品，每中物品都有自己的重量 和 价值，在限定的总重量 / 总容量(C)内，选择其中若干个(每种物品可以选 0 个或 1 个)，设计选择方案使得物品的总价值最高.

　　对于可分背包问题，直接使用贪心算法即可得到最优解，但是贪心算法并不适用于 0-1 背包问题，需要使用动态规划的思想.
　　动态规划的解法常需要写出一个递推或者状态转移公式描述问题的最优解的状态，对于 0-1 背包问题而言，推导如下

　　定义子问题 为: 在前 i 个物品中挑选总重量不超过 W 的物品，每种物品最多挑选 1 个，使得总价值最大，这时的最优值记作 m(i, W)，其中 .
　　考虑第 i 个物品，无非两种选择，选或者不选．

  • 不选的话，背包的容量不变，改变为问题 .
  • 选的话，背包的容量变小，改变为问题

　　最优方案就是比较这两种方案，取其中的最大值

　　算上边界情况，可得如下状态转移方程

　　递归实现

1
2
3
4
5
6
7
8
9
10
11
/** i 表示第 i 个物品， w 表示当前的剩余容量，*/
int P(int i, int W, vector<int>& w, vector<int>& v)
{
    if (i == 0)
        return 0;
    if (W == 0)
        return 0;
    if (w[i] > W)
        return P(i - 1, W, w, v);
    return max(P(i - 1, W, w, v), v[i] + P(i - 1, W - w[i], w, v));
}

　　二维表方式实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

/** @param W 各物体重量
 *  @param V 各物体价值
 *  @param C 背包总容量
 * */
int P(vector<int>& W, vector<int>& V, int C)
{
    using Matrix = vector<vector<int>>;
    Matrix mat (W.size() + 1, vector<int>(C + 1, 0));
    for (int i = 1; i <= W.size() ; ++i)
    {
        for (int w_ = 1; w_ <= C; ++w_)
        {
            if (W[i] > w_)
                mat[i][w_] = mat[i - 1][w_];
            else 
                mat[i][w_] = max(mat[i - 1][w_], V[i] + mat[i - 1][w_ - W[i]]);
        }
    }
    return mat[W.size()][C];
}