背包问题
01背包
01背包主要解决的问题就是选or不选的情况。枚举选了当前物品后的状态转移,而选当前物品之前的状态可以通过减去当前体积得到。
01背包分为两种,一种是固定容量,求能得到的最大价值。一种是确定最小价值,求可能的方案数量。有些类似对偶问题。
1. 最大价值解
模板题
物品只能使用一次,每个物品有不同的价值和体积,如何在给定容量选取物品得到最大价值。
关键点:
- 状态如何定义
- 子问题确定
- 如何枚举
物品的最大价值是需要求的,最大价值与选取哪些物品有关,而物品有两种属性(体积、价值)。令总价值为状态的值,而背包的容量为状态变量,其含义为容量为v的背包的最大价值。因为需要枚举物品,因此增加一维表示物品。
那么其子问题就是在前面n-1
个物品使用v
个体积所能达到的最大价值。
枚举的时候需要枚举容量,当前物品若能放下,则其转移为:
- 一维优化
1 | for (int i = 1; i <= n; ++ i) cin >> v[i] >> w[i]; |
- 二维空间
1 | for (int i = 1; i <= n; ++ i) cin >> v[i] >> w[i]; |
分割等和子集
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。
- 关键点
首先需要根据题目推出 目标是求一个子序列满足 其和为总和的一半。那么这个问题可以看作体积与价值相同的背包问题,并且容量是总和的一半。体积与价值相同便限制了加入背包的数之和(体积用于限制和,价值用于接近和)。
1 | bool canPartition(vector<int>& nums) { |
一和零
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的大小,该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素,集合 x 是集合 y 的 子集 。
即给出一些物品,它们包含一和零,给出1和0的容量m,n。求最多物品的数量。相比于模板01背包,多了一维容量。直接当成二维来做就好了。
1 | int findMaxForm(vector<string>& strs, int m, int n) { |
最后一块石头的重量II
有一堆石头,每块石头的重量都是正整数。
每一回合,从中选出任意两块石头,然后将它们一起粉碎。假设石头的重量分别为 x 和 y,且 x <= y。那么粉碎的可能结果如下:
如果 x == y,那么两块石头都会被完全粉碎;
如果 x != y,那么重量为 x 的石头将会完全粉碎,而重量为 y 的石头新重量为 y-x。
最后,最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下,就返回 0。
使得消除后的石头重量最小,实际上也就是将它们分为质量最相近的两份,那么与分割等和子集就差不多了。
1 | int lastStoneWeightII(vector<int>& stones) { |
2. 最优解的方案数
组合总和IV
给定一个由正整数组成且不存在重复数字的数组,找出和为给定目标正整数的组合的个数。
题目即求和为target的子序列的方案数,做法就是枚举1到target之间的所有可能值,计算其方案数,当前的目标值的方案数 += 选择当前数 之前的状态方案数,类似记忆化搜索。
1 | int combinationSum4(vector<int>& nums, int target) { |
目标和
给定一个非负整数数组,a1, a2, …, an, 和一个目标数,S。现在你有两个符号 + 和 -。对于数组中的任意一个整数,你都可以从 + 或 -中选择一个符号添加在前面。
返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
题目要求在数组中为一部分选择+,一部分选择 - ,那么每个物品有三种选择:1. 不选, 2. 选+ ,3. 选 - 。这样不好处理。将问题变换一下,令选择 + 的部分为a, 选择 - 的部分为 b,那么:
同时,若a确定,则b确定,因此可将目标设为求 a ,这样就转化为了分割等和子集。稍有区别的是它求的是方案数,但枚举方法是一样的,类似记忆化,需要用到上一个物品选择后的dp状态,因此内层容量倒序枚举。
1 | int findTargetSumWays(vector<int>& nums, int S) { |
盈利计划
集团里有 n 名员工,他们可以完成各种各样的工作创造利润。
第 i 种工作会产生 profit[i] 的利润,它要求 group[i] 名成员共同参与。如果成员参与了其中一项工作,就不能参与另一项工作。
工作的任何至少产生 minProfit 利润的子集称为盈利计划。并且工作的成员总数最多为 n 。
有多少种计划可以选择?因为答案很大,所以 返回结果模 10^9 + 7 的值。
1 | int profitableSchemes(int G, int P, vector<int>& group, vector<int>& profit) { |
其他背包
完全背包
物品可无限使用
物品可选无限次,那么dp更新的时候公式就变化了
而注意到
可以看出二式相比于一式的后面只少了w,因此
完全背包与01背包公式不同的地方只是在更新的时候用的是本层的物品$i$,所以他们的枚举方式有细微区别,完全背包从前往后枚举即可。
对比01背包公式:
1 | for (int i = 1; i <= n; ++ i) cin >> v[i] >> w[i]; |
多重背包
物品限制了件数