Letcode 背包问题一览

,

背包问题(Knapsack problem)是一种组合优化的 NP 完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量 w 和价格 v ，在限定的总重量内，我们如何选择，才能使得物品的总价格 V 最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。
背包问题可以分为很多的种类,但是各类复杂的背包问题总可以变换为简单的0-1背包问题进行求解[4],下面将详细的介绍背包问题的一些“共性”。

1. 背包问题的分类及模板

  1. 0-1背包问题：每个元素最多选取一次
  2. 完全背包问题：每个元素可以重复选择
  3. 多重背包问题：不止一个背包，需要遍历每个背包
  4. 组合背包问题：背包中的物品要考虑顺序
  5. 分组背包问题：这个比较特殊，需要三重循环：外循环背包bags,内部两层循环根据题目的要求转化为1,2,3三种背包类型的模板

1.1 代码模板

背包问题通常使用动态规划的思想来解决，这意味着背包问题是“有迹可循”的.
背包问题的模板如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    /* 
        coins : 每一个物品
        amount: 背包的容量
        dp[i] 储存当背包容量为 i 时符合题意的解答
    */
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount  + 1);
        dp[0] = 0; 
        for(int i = 1; i <= amount; i ++) { //遍历所有的容量
            for(int j = 0; j < coins.size(); ++j){ //遍历所有的物品
               // 转移方程
            }
        }
        return dp[amount ];
    }
};

但切记不可死套模板，不同的题会有不同的要求,有时甚至要借助其他的数据结构才能解答,所以要要灵活的使用,适当的对代码做出修改是有必要的

1.2 转移方程

在 [1] 中，作者针对不同的背包的不同要求，将问题分为三类,分别是最值问题、存在问题、组合问题，并给出来了对应的转移方程

  1. 最值问题,要求满足条件的最大值/最小值: dp[i] = max/min(dp[i], dp[i-nums]+1) 或
    dp[i] = max/min(dp[i], dp[i-num]+nums);
  2. 存在问题,是否存在?(bool)：dp[i]=dp[i] || dp[i-num];
  3. 组合问题,满足条件的组合：dp[i] += dp[i-num];

    这里并不可能列出所有的转移方程(尤其是对于混合背包问题)

2. 0-1 背包问题

如果限定每种物品只能选择0个或1个，则问题称为0-1背包问题。

例题 416. 分割等和子集

1
2
3
4
5
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例：
    输入：nums = [1,5,11,5]
    输出：true
    解释：数组可以分割成 [1, 5, 5] 和 [11] 。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool canPartition(vector<int> &nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum % 2 == 1)  //如果是和为奇数显然无法分成两个等和子集
            return false;
        int target = sum / 2; 
        vector<int> dp(target + 1, 0); //dp[i]:是否存在子集和为i
        dp[0] = true;   //初始化：target=0不需要选择任何元素，所以是可以实现的
        for (int num : nums) //所有的物品
            for (int i = target; i >= num; i--) //所有的容量
                //转移方程2
                dp[i] = dp[i] || dp[i - num];
        return dp[target];
    }

};

3. 完全背包问题

求解：将哪些物品装入背包，可使这些物品的耗费的费用总和不超过背包容量，且价值总和最大。
这个问题非常类似于0-1背包问题，所不同的是每种物品有无限件。也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取0件、取1件、取2件……等很多种。
转移方程为: 最值问题的第一种形式

例题 leetcode 322. 零钱兑换

1
2
3
4
5
6
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。你可以认为每种硬币的数量是无限的。

示例:
    >输入：coins = [1, 2, 5], amount = 11
    >输出：3 
    >解释：11 = 5 + 5 + 1

解答:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        //初始化为 amount + 1,比所有的数都大
        vector<int> dp(amount  + 1, amount + 1);
        dp[0] = 0;
        for(int i = 1; i <= amount; i ++) {//遍历所有的容量
            for(int j = 0; j < coins.size(); ++j){ //遍历所有的物品
                if(coins[j] <= i) //使 转移方程中的 i - coins[j] 有效
                    //属于最值问题,使用转移方程1
                    dp[i] = min(dp[i], dp[i - coins[j]] + 1);
            }
        }
        // 如果 dp[amount] 的值为amount + 1,则表示没有一种硬币组合能组成总金额.
        return dp[amount ] == amount + 1  ? -1 : dp[amount];
    }
};

4. 多重背包问题

求解将哪些物品装入背包可使这些物品的耗费的空间总和不超过背包容量，且价值总和最大.
和完全背包问题很类似。基本的方程只需将完全背包问题的方程略微一改即可。
转移方程为: 最值问题的第二种形式

例题 1049. 最后一块石头的重量 II
与 上面的完全背包问题类似,但对于题目给的初值进行了处理,在返回时也不是直接返回 dp[amount]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。
示例:
    >输入：stones = [2,7,4,1,8,1]
    >输出：1
    >解释：
        组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
        组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
        组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
        组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 求解 sum /2 可装最大价值 MaxValue,返回结果为 sum - 2 * MaxValue
class Solution {
public:
    int lastStoneWeightII(vector<int> &stones) {
        int sum = accumulate(stones.begin(), stones.end(), 0);
        int target = sum / 2;
        vector<int> dp(target + 1);
        for (int stone : stones)
            for (int i = target; i >= stone; i--)
                //转移方程1的第二类
                dp[i] = max(dp[i], dp[i - stone] + stone);
        return sum - 2 * dp[target];
    }
};

5. 组合背包问题

求解的是物品的组合问题,例如有多少种组合使得背包能够装满等,通常会有一些额外的限制,例如组合不能重复，只能按照规定的限制进行选取等。
这时最可能想到 回溯 算法，但是会超时…

例题 leetcode 518. 零钱兑换 II

1
2
3
4
5
6
7
8
9
10
11
12
13
给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。
示例:
    >输入：amount = 5, coins = [1, 2, 5]
    >输出：4
    >解释：有四种方式可以凑成总金额：
        5=5
        5=2+2+1
        5=2+1+1+1
        5=1+1+1+1+1

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int change(int amount, vector<int> &coins)
{
    vector<int> dp(amount + 1);
    dp[0] = 1;
    // 要考虑顺序问题,所以物品遍历在外面，背包遍历在里面,否则会有重复的组合
    for (int coin : coins) 
        for (int i = 1; i <= amount; i++)
            if (i >= coin)
            //属于组合问题,使用转移方程3
                dp[i] += dp[i - coin];
    return dp[amount];
}
};

377. 组合总和 Ⅳ 与这道题类似,但是因为不考虑顺序,所以不必考虑循环的次序.而且,因为有溢出的问题,所以if条件更为严格 “if( i >= nums[j] && dp[i - nums[j]] < INT_MAX - dp[i])”

6. 分组背包

物品被划分为 K 组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

例题 1155. 掷骰子的N种方法

1
2
3
4
5
6
7
8
9
这里有 d 个一样的骰子，每个骰子上都有 f 个面，分别标号为 1, 2, ..., f。

我们约定：掷骰子的得到总点数为各骰子面朝上的数字的总和。

如果需要掷出的总点数为 target，请你计算出有多少种不同的组合情况（所有的组合情况总共有 f^d 种），模 10^9 + 7 后返回。

示例：
    >输入：d = 1, f = 6, target = 3
    >输出：1

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/*
    骰子被分为了d 组,每组有 f 个物品,每次只能选择其中的一个.
    d 个骰子，每个骰子可以取 1~f 中的任意一个值
    这里有两个背包问题,一个可以看作是 0-1 背包问题
    分组背包问题将这两者组合起来了
    dp[i][j] 表示投掷i个骰子点数和为j的方法数
即: dp[i][j] 表示 前i组物品的总重量为 j 时取得的最大价值

    所以应该是分组背包 的 组合问题,转移方程类似于上面的转移方程3
*/
int numRollsToTarget(int d, int f, int target)
{
    vector<vector<int>> dp(d + 1, vector<int>(target + 1, 0));
    dp[0][0] = 1;
    //三层循环：最外层为背包d,然后先遍历target后遍历点数f
    for (int i = 1; i <= d; i++) // 遍历所有组
        for (int j = 1; j <= target; j++)//遍历所有重量
            for (int k = 1; k <= f && j >= k; k++) //遍历所有组内的所有元素
                //扩展之后的转移方程3
                dp[i][j] += dp[i - 1][j - k];
    return dp[d][target];
}

参考

  1. 一篇文章吃透背包问题！

  2. 深度讲解背包问题

  3. 背包问题九讲

  4. 杨克昌．计算机常用算法与程序设计案例教程 第2版．北京：清华大学出版社 ，2015