背包问题总结——剑指offer二专项101-104

01背包

有n件价值不同的物品和一个最多能背重量为w 的背包，求解将哪些物品装入背包里物品价值总和最大。

动态规划二维数组

使用动态规划，那就离不开二维数组

对于确定每一个格子的数据，横向表示针对某个物品，纵向表示针对某个重量，那么这个格子有两种方式：一个是能够放入这个物品，另一个是放不进这个物品。

递推式，即dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
初始化：

遍历顺序：
横向和纵向都可以

下面图不准确，dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 应该是上一行的同列元素和左上角，并不是同行的元素，没有用到本行的元素。


填满以后，获得最右下角的元素就是答案。

void test_2_wei_bag_problem1() {
    vector<int> weight = {1, 3, 4};
    vector<int> value = {15, 20, 30};
    int bagweight = 4;

    // 二维数组
    vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));

    // 初始化
    for (int j = weight[0]; j <= bagweight; j++) {
        dp[0][j] = value[0];
    }

    // weight数组的大小 就是物品个数
    for(int i = 1; i < weight.size(); i++) { // 遍历物品
        for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
            if (j < weight[i]) dp[i][j] = dp[i - 1][j];
            else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

        }
    }

    cout << dp[weight.size() - 1][bagweight] << endl;
}

int main() {
    test_2_wei_bag_problem1();
}

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

动态规划一维数组

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

递推公式变为dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}
1
2
3
4
5

上面类似二维数组中横向遍历，但这里是横向从后向前遍历，一直往前遍历到不能存放当前物品的重量（不能存放就不用遍历了），为了好理解，还是全遍历了好。

可以看到使用的是上一行的同列元素和左上角元素，因此不能从左向右移动，这样会覆盖上一层的元素，因为没有使用当前行的元素，因此可以从后向前移动，

void test_1_wei_bag_problem() {
    vector<int> weight = {1, 3, 4};
    vector<int> value = {15, 20, 30};
    int bagWeight = 4;

    // 初始化
    vector<int> dp(bagWeight + 1, 0);
    for(int i = 0; i < weight.size(); i++) { // 遍历物品
        for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    cout << dp[bagWeight] << endl;
}

int main() {
    test_1_wei_bag_problem();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

剑指 Offer II 101. 分割等和子集

给定一个非空的正整数数组 nums ，请判断能否将这些数字分成元素和相等的两部分。

输入：nums = [1,5,11,5]
输出：true
解释：nums 可以分割成 [1, 5, 5] 和 [11] 。

让target为所有元素加起来除以二，如果为偶数那么继续，否则结束（不能分为两个）
同样有两种选择，第一种是容量能够放入当前元素，一个是不放入当前元素

这里直接用一维数组

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;

        // dp[i]中的i表示背包内总和
        // 题目中说：每个数组中的元素不会超过 100，数组的大小不会超过 200
        // 总和不会大于20000，背包最大只需要其中一半，所以10001大小就可以了
        vector<int> dp(10001, 0);
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
        }
        if (sum % 2 == 1) return false;
        int target = sum / 2;

        // 开始 01背包
        for(int i = 0; i < nums.size(); i++) {
            for(int j = target; j >= nums[i]; j--) { // 每一个元素一定是不可重复放入，所以从大到小遍历
                dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
        // 集合中的元素正好可以凑成总和target
        if (dp[target] == target) return true;
        return false;
    }
};
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

这里为什么是dp[target] == target

01背包中，dp[j] 表示： 容量为j的背包，所背的物品价值可以最大为dp[j]
套到本题，dp[j]表示： 背包总容量是j，最大可以凑成j的子集总和为dp[j]
dp[j]的数值一定是小于等于j的

for(int i = 0; i < nums.size(); i++) {
    for(int j = target; j >= nums[i]; j--) { // 每一个元素一定是不可重复放入，所以从大到小遍历
        dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
    }
}
1
2
3
4
5

完整代码

#include 
#include 

using namespace std;

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;

        // dp[i]中的i表示背包内总和
        // 题目中说：每个数组中的元素不会超过 100，数组的大小不会超过 200
        // 总和不会大于20000，背包最大只需要其中一半，所以10001大小就可以了
        vector<int> dp(10001, 0);
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
        }
        if (sum % 2 == 1) return false;
        int target = sum / 2;

        // 开始 01背包
        for (int i = 0; i < nums.size(); i++) {

            cout <<"nums[i]"<<" "<<nums[i]<<"         ";
            for (int j = target; j >= nums[i]; j--) { // 每一个元素一定是不可重复放入，所以从大到小遍历
                dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
            }
            for (int k = 0; k <= target; k++)
            {
                cout << dp[k] << "  ";
            }
            cout << "\n";
        }
        // 集合中的元素正好可以凑成总和target
        if (dp[target] == target) return true;
        return false;
    }
};

int main() {
    vector<int> v = { 1,5,11,5 };
    Solution s;
    cout<<s.canPartition(v);
}
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

还有一个思路，数组格子里存放true或者false，dp[i][j]如果已经装满则用true表示，如果没有装满用false表示。在递推式看上行同列和左上角，只要有一个为true那么本格子就是true

class Solution1 {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for (auto& n : nums) {
            sum += n;
        }
        if ((sum & 1) != 0) {
            return false;
        }

        int target = sum >> 1;
        vector<vector<bool>> dp(nums.size() + 1, vector<bool>(target + 1, false));
        dp[0][0] = true;
        for (int i = 1; i <= nums.size(); ++i) {
            for (int j = 0; j <= target; ++j) {
                dp[i][j] = dp[i - 1][j];//不将本元素放入数组格子内
                if (!dp[i][j] && j >= nums[i - 1]) { //j >= nums[i - 1]是下面用到怕数组越界
                    dp[i][j] = dp[i - 1][j - nums[i - 1]]; //j - nums[i - 1]是将本元素放到格子内
                }
            }
        }
        return dp[nums.size()][target];
    }
};
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

使用一维数组

剑指 Offer II 102. 加减的目标值

给定一个正整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 ‘+’ 或 ‘-’ ，然后串联起所有整数，可以构造一个 表达式 ：

例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-’ ，然后串联起来得到表达式 “+2-1” 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

这里元素只能使用一次因此是01背包问题

将一部分元素放到正集合里面，将另一部分放到负集合里面，只要将正集合里面的元素都赋为正值，将负集合里面的元素赋为负值且要求正集合的和和负集合的和相等，那么就是上面的分割等号子集的问题

这里设正集合的数字之和为p，负集合为q，那么p-q=target，设p+q=sum，那么两式相加为p = (sum + target) / 2或者得出q = (sum - target) / 2

这里二维数组的每个格子都代表到这个格子有几种方法，注意这里每个格子都认为是被填满的，也就是

到达当前点有两种方法，一种是背包本身已经被填满，也就是同列上行。另一种是加上本物品就会填满，也就是找f(i-1,j-nums[i]) （就像上面说的，重点在于j-nums[i]）。

二维降为一维同样也是

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = 0;
        for (auto& n : nums) {
            sum += n;
        }

        int newTar = sum + target; //获得新的目标值

        if ((newTar & 1) != 0 || newTar < 0) { //排除奇数和小于0的情况
            return 0;
        }

        vector<int> dp(newTar / 2 + 1, 0);
        dp[0] = 1;
        for (auto& n : nums) {
            for (int j = dp.size() - 1; j >= n; --j) { // j >= n表示我还能存放下这个物品
                dp[j] += dp[j - n];//每次都要求自己是被填满的有两种方式 一个是同列上行，另一个是左上角
            }
        }
        return dp.back();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

剑指 Offer II 103. 最少的硬币数目（完全背包问题）

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

你可以认为每种硬币的数量是无限的。
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1

这里元素能使用多次，因此不再是01背包问题。

-----------------------------错误分割线
以下面这个图作为理解，现在加上金币5的条件，我想凑够20，有两种选择，一种是我不理你这个金币5直接用同列上行的数据，另一种就是我要加上这个金币5，加这个金币5我可以加一个，也可以加多个，所以射向左上角的方向箭头有多个，这个怎么处理？？看这图的下面

还有一个问题，那就是第一种选择用同列上行的数据那么由于求的最小值，那么可以用同列上上行的数据吗？ 答案是不能，因为上行是根据上上行做出的最优的选择，所以上行就是最优的选择了，本行只用上一行的数据就行了，不用上上行的数据。

---

有两种选择，一个是不加入这个金币，那么就是同列上一行（金币已经凑满，不会因为本金币的加入而有影响），另一个是加入这个金币，那么这里的思路就和01背包完全不同，这里是在已有本金币参与的影响去扩大背包的大小，就是在同行不同列。

第二种思路：按列迭代
抽象成1维，每列表示的是凑成当前列总额的最少硬币个数，比如dp[10] =3，那么凑成总额为10的硬币最少个数为3，不关心是用什么凑得，在此基础上进行下一列dp[11]，默认让dp[11]为最大值，然后dp[11-1]+1尝试加上这个硬币，具体思路看下面的图

剑指 Offer II 104. 排列的数目

给定一个由 不同 正整数组成的数组 nums ，和一个目标整数 target 。请从 nums 中找出并返回总和为 target 的元素组合的个数。数组中的数字可以在一次排列中出现任意次，但是顺序不同的序列被视作不同的组合。

题目数据保证答案符合 32 位整数范围。

输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。

这个题和上面第二种解法一样，区别在于上面是找最小值，这里是全加起来

只要能凑成当前的总额那么就加起来

题目总结

先看知识总结

01背包问题
分割等和子集
加减的目标值
最少的硬币数目
排列的数目

用二维数组表示，列向表示最大重量，横向表示物品

1)01背包问题 （01背包）

有n件价值不同的物品和一个最多能背重量为w 的背包，求解将哪些物品装入背包里物品价值总和最大。

二维数组求最大价值，通过先遍历物品再遍历背包重量
   在指定一个坐标后，是从前面小重量过来的，也就是增加了背包的最大承受重量
   我可以使用同列上行的数据看它的价值，
   也可以使用加上我这个物品，也就是左上角元素
前面已经遍历的格子已经默认在它的视角是最大价值
也可以将二维抽象成一维，那么只能从右向左遍历，由于我想要使用左上角的数据，如果从左向右，那么本行的数据将会覆盖上一行的数据
1
2
3
4
5
6
7
8

2)分割等和子集（01背包）

01背包，每个元素只能用一次

给定一个非空的正整数数组 nums ，请判断能否将这些数字分成元素和相等的两部分
	分成元素和相等的两部分，将和加起来除以二，这就是目标值。题目也就变成了存放物品重量到规定的背包容量
	元素和如果是偶数则继续，否则结束
第一种做法： 格子存放物品的重量
第二种做法：  要求前面的所有格子都是满的
	先遍历行再遍历列
	指定一个格子，到这个格子有两种方法，一种是同列上行已经填满，一种是我加上本物品
	这两种方法只要有一个是true那么本格子就赋值为true，否则false
	然后一直遍历到最后，只要到最左下角为true那么就是true
第二种方法降维到一维，因为是上行同列和左上角，如果从左向右遍历那么就会覆盖上行的数据，因此要从右向左遍历
	
1
2
3
4
5
6
7
8
9
10
11

3)加减的目标值（01背包）

01背包，每个元素只能用一次

给定一个数组，赋予其元素加减号，让其加减后为目标值

设正集合的数字之和为p，负集合为q，那么p-q=target，设p+q=sum，那么两式相加为p = (sum + target) / 2或者得出q = (sum - target) / 2

对于给的数，让它凑成目标值，上面题是凑成sum/2，这里是凑成(sum - target) / 2，都是确定的目标值
不同在于是看有几种方法，上题是针对同列上行和左上角有一个true本格子就是true
这里是将格子里面的数字加起来，也就是将同列上行和左上角的和加起来
1
2
3
4
5
6
7

4)最少的硬币数目（完全背包）

元素可以使用多次

第一种做法：正常先行再列
	由于硬币可以使用多次，这里直接同行不同列和同列不同行两个方向
	对比从这两个方向是求最小值
第二种做法：先列后行
	这种做法使用用一维数组做，每个元素代表这一列最小的硬币数量，这个看上面思路
1
2
3
4
5

4)排列的数目（完全背包）

	和上题第二种做法类似，是直接加起来将数量而不是求最小值
1

背包知识总结

01背包和完全背包的区别（重要）

背包类型（重要）

1、能否组成
2、有几种方式
3、最少

1）能够组成

要求前面的格子都能唯一确定能不能组成，也就是true和false

2）有几种方式

方向加起来

3）最少

方向求min