0-1 Package
例题讲解
基础的零一背包
给定 背包容量和两个数组.两数组分别代表各物品的价值和体积.
求 给定背包容量内的最大价值
零一背包中的零一指的是两种状态 0:不选择 1:选择 每次不同的容量和不同的物品都要作出一次 零一判断
而最终结果由之前的状态或者选择所决定 决定最终背包中所装物品的属性两个 容量 价值 dp[物品][容量] 最终返回时返回的 dp[最后一个物品][给定背包容量]
有 a b c d 物品 属性 分别是
c(体积) 1 3 2 v(价值) 2 4 6 给定背包容量为 5
| 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| a | 2 | 2 | 2 | 2 | 2 |
| b | 2 | 2 | 4 | 6 | 6 |
| c | 2 | 6 | 8 | 8 | 10 |
横向0 1 2 3 4 5代表着当背包容量为n时的最大价值 纵向 a b c 则代表着 当前选择放入的物品 (x, y) –> (a, 1) == 当容量为 1 时 当前是否放入物品 a 判断过程: 1 >= a 体积 可选择放入 当放入后剩余空间 1-a 体积 == 0, 比较 空间为 0 时的最大价值 + a 的价值 和 上一个物品的在当前容量下的最大价值. 返回最大值
for (int i = 1; i <= obj.size(); i++) {
for (int j = 0; j < cap; j++) {
if (j < c[i-1]) {
dp[i][j] = dp[i-1][j];
}
else{
dp[i][j] = max(dp[i-1][j], dp[i-1][j-c[i-1]]+ v[i-1]);
}
}
}
应先初始化 dp[0][j] = 0;
因为当容量为0时,价值只能为0
LC416 分割等和子集
给定一个 非0正整数数组, 判断是否可以分为n两个子数组 使得 arr1 == arr2
也就是 arr1 + arr2 = sum
首先可以通过和是否为偶数来判断 sum & 1 == 1 return false;
题目要求判断是否可分而不是要求找出两个子集 所以问题可转化成 是否可以在 数组中凑出和为 sum / 2 就可以 转换成 容量为n的背包 是否可以找出一系列物品恰好装满 因为每次是在判断能否恰好装满,所以只需要记录是否可以装满即可 c(体积) 1 3 2
| 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| a | true | false | false | false | false |
| b | true | false | true | true | false |
| c | true | true | true | true | true |
dp[arr.size()+1][sum/2 + 1];
此处也应先初始化 dp[0][j] = true;
因为 0 无需放入元素即可满足.
判断过程
当前物品体积 > 容量 –> 不满足,填入上一行的结果
当前物品体积 <= 容量 –> 满足,填入上一行减去物品体积后对应结果
for (int i = 1; i < arr.size()+1; i++) {
for (int j = 0; j < sum/2 +1; j++) {
if (j < arr[i-1]) dp[i][j] = dp[i-1][j];
dp[i][j] = dp[i][j - arr[i-1]];
}
}
若按这种方式遍历会出现严重逻辑错误,因为当从左到右更新时可能会使用到前一次更新的值. 因此需要倒序遍历,避免这种情况.
for (int i = 1; i < arr.size() + 1; i++){
for (int j = sum/2; j >= 0; j--) {
if (j < arr[i-1]) dp[i][j] = dp[i-1][j];
else dp[i][j] = dp[i-1][j- arr[i-1]] || dp[i-1][j];
if (dp[i][sum/2] == 1) return true;
}
}
采用倒序遍历后有许多点需要注意:
-
初始化问题,采用正序遍历时因为从下标 1 开始所使用的值都是已经正确赋值过的, 所以可以不初始化后续,但后续遍历就会出现相应问题, 所以需要统一初始化或者使用 STL 中的
vector解决初始化问题.- 倒序遍历时不能在同一行"减去"容量,因为i此时i还没有继承上一行已更新的值,
所以为规范写法统一为
dp[i][j] = dp[i-1][j - arr[i-1]]. - 继承问题,与第二点相同,“减去"容量后发现无法凑出不会去继承上一行已有的结果,所以加入
|| dp[i-1][j];.
- 倒序遍历时不能在同一行"减去"容量,因为i此时i还没有继承上一行已更新的值,
所以为规范写法统一为
LC1049 最后一块石头的重量 II
给定一个数组 arr, 每次选出两个数 “碰撞” 返回abs(x-y),直至只剩一个数字返回它可能的最小值.
要求最小的最后一块石头重量,我们可以模拟一下步骤.
[31,26,33,21,40]
33 - 31 = 2 40 - 26 = 14 21 - 14 = 7 14 - 7 = 7 7 - 2 = 5
可以发现 我们每次是进行 如下操作 分为两堆石头
[33, 40] - [31, 26] 将剩余石头放回 [2, 14, 21]
[21] - [14] [7, 2]
[7] - [2] [5]
假设有 n个石头那么可以分成
[a1, a2, ..., an/2] - [b1, b2, ..., bn/2]
但是每次这样分放太过麻烦,其实可以直接转化成两个子序列问题,此时就与 LC416基本相同.
可以转化的推导过程如下:
(a1+a2+a3+a4) - (b1+b2+b3+b4) = sum if a1-b1 > 0 (a2+a3+a4+(a1-b1)) - (b2+b3+b4) —> (a1+a2+a3+a4) - b1 -(b2+b3+b4)
if a1 - b1 < 0 (a2+a3+a4) - (-(a1-b1)+b2+b3+b4) —> (a2+a3+a4) + a1 - (b1+b2+b3+b4) 从推导过程可看出每次碰撞产生的新石头再次加入到碰撞中与之前相同,所以无需每次分放.
那么任务就是 找出arr1 + arr2 = arr并且使得 arr1 - arr2最小,这时我们发现其与 LC416的相似处.
可以通过找arr1 == sum/2 然后 sum -= 2*arr1 获得最小值.
for (int i = 1; i < stones.size()+1; i++) {
for (int j = 1; j < sum/2 +1; j++) {
if (j >= stone[i-1]) {
dp[i][j] = dp[i-1][j] || dp[i-1][j-stones[i-1]];
}
else {
dp[i][j] = dp[i-1][j];
}
}
}
for (int j = sum/2 ; j >= 0; j--) {
if (dp[stones.size()][j] == true) {
sum -= 2*j;
break;
}
}
LC494.目标和
给定一个数组和一个目标值,要求对这些数添加”+“和”-",找出使和为目标值的所有组合次数.
一组数 如 1, 1, 1, 1, 1; 目标值为3, 那么就有 1 - 1 + 1 + 1 + 1 = 3 1 + 1 - 1 + 1 + 1 = 3 1 + 1 + 1 - 1 + 1 = 3 1 + 1 + 1 + 1 - 1 = 3 -1 + 1 + 1 + 1 + 1 = 3 所有能组合为3的情况有5种
此时问题就是必须把所有物品放入背包,每个物品有两种状态"+“和”-",这两种状态与0与1基本一致,那么背包的容量范围就是[-sum, sum],于是可以写出如下代码.(这里很像一次操作,是在背包内减去或者加入体积为arr[index]的物品)
vector<<vector<int>> dp(arr.size()+1, vector<int>(sum*2+1, 0));
dp[0][sum] = 1;
这里需要强调的是初始化问题,在之前的题中我们基本是将所有行的 0 处初始化,而这里只初始化 0 行的 sum 为一.
首先因为容量范围是 -sum 到 sum ,下标是 0 到 sum*2+1,产生了偏移,所以和为 0 时下表对应着 sum.
其次是只初始化 0 行的问题, 每行中的一个数都是代表着在(-1, index-1]的子序列中可以组合出当前数的次数,当index = 0 + sum; 时表示arr的子序列 { },此时不存在元素 所以可以使得和为 0, 如果将所有行的sum处初始化为零就不符合情况了.
比如当前子序列是 {1},不可能出现和为0的情况.
for (int i = 1; i < arr.size()+1; i++) {
for (int j = 0; j < 2*sum+1; j++) {
if (j - arr[i] >= 0) { //防止越界
dp[i][j] += dp[i-1][j-arr[i-1]];
}
if (j + arr[i] <= 2*sum) {
dp[i][j] += dp[i-1][j+arr[i-1]];
}
}
}
LC.474 一和零
给一个二进制字符串和两个整数m与n,找出一个该数组的最长子集,子集内部的 0和1数量小于等于m和n,返回该子集长度.
再次回顾一下零一背包, 零一背包通常是在有限的容量求最大价值,或是特定的容量求特定价值.
一般的零一背包只有一个限制,而本题则同时有两个限制m和n,相当于既要能装入最大容量为m的背包又能装入最大容量为n的背包.
所以我们需要初始化一个三维数组
int dp[arr.size()+1][m+1][n+1]; //vector<vector<vector<int>>> dp(strs.size()+1, vector<vector<int>>(m+1,vector<int>(n+1,0)));
然后是核心逻辑的实现,我们要同时满足m和n,所以额外的判断如下
if (j >= msize && k >= nsize) {
//.....
}
其余部分和普通零一背包基本相同
for (int k = 1; k < strs.size()+1; k++) {
int msize = count(strs[k-1].begin(), strs[k-1].end(), '0');
int nsize = strs[k-1].size() - msize;
for (int i = m; i >= 0; i--) {
for (int j = n; j >= 0; j--) {
if (j >= nsize && i >= msize) {
dp[k][i][j] = max(dp[k-1][i][j], dp[k-1][i-msize][j-nsize]+1);
}
else {
dp[k][i][j] = dp[k-1][i][j];
}
}
}
}
问题的基本解法已经讲完,我们现在来对每个问题进行梳理.
问题分析
特征提取
-
原始零一背包
-
给定 物品(体积 + 价值) 和 背包容量
-
求 最大价值(选择物品体积小于等于背包容量时的最大价值)
-
-
分割等和子集
-
给定 物品(只有体积) 和 背包容量(需要凑出的sum/2)
-
求 最大容量是否可以装满(选择物品体积是否可以等于背包最大容量)
-
-
最后一块石头重量II
-
给定 物品(只有体积) 和 背包容量
-
求 最大容量(能够凑出的最大体积)
-
-
目标和
-
给定 物品(只有体积) 和 背包(容量不定)
-
求 特定体积(让背包体积刚好等于目标值)
-
-
一和零
-
给定 物品(价值相同,体积不同) 和 两个背包
-
求 最大价值(选择物品体积同时小于等于两个背包的最大体积)
-
通过上面对比和上述题解可以发现,零一背包的特征总是:
- 给定的数据为离散数据,且只能选择一次不可复用.
- 决策通常只有选择与不选择且常受条件限制(比如当前容量)
- 求解目标往往是求最优解或者验证最优解是否可行
- 每一个解都由前一步和当前情况共同决定,最终结果由初始结果递推得来.
- 获得最终解往往需要穷尽所有组合
思考过程
示例
金明的预算方案
题目描述
金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过 $n$ 元钱就行”。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：
| 主件 | 附件 |
|---|---|
| 电脑 | 打印机，扫描仪 |
| 书柜 | 图书 |
| 书桌 | 台灯，文具 |
| 工作椅 | 无 |
如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有 $0$ 个、$1$ 个或 $2$ 个附件。每个附件对应一个主件，附件不再有从属于自己的附件。金明想买的东西很多，肯定会超过妈妈限定的 $n$ 元。于是，他把每件物品规定了一个重要度，分为 $5$ 等：用整数 $1 \sim 5$ 表示，第 $5$ 等最重要。他还从因特网上查到了每件物品的价格（都是 $10$ 元的整数倍）。他希望在不超过 $n$ 元的前提下，使每件物品的价格与重要度的乘积的总和最大。
设第 $j$ 件物品的价格为 $v_j$，重要度为 $w_j$，共选中了 $k$ 件物品，编号依次为 $j_1,j_2,\dots,j_k$，则所求的总和为：
$$v_{j_1} \times w_{j_1}+v_{j_2} \times w_{j_2}+ \dots +v_{j_k} \times w_{j_k}$$
请你帮助金明设计一个满足要求的购物单。
输入格式
第一行有两个整数，分别表示总钱数 $n$ 和希望购买的物品个数 $m$。
第 $2$ 到第 $(m + 1)$ 行，每行三个整数，第 $(i + 1)$ 行的整数 $v_i$，$p_i$，$q_i$ 分别表示第 $i$ 件物品的价格、重要度以及它对应的的主件。如果 $q_i=0$，表示该物品本身是主件。
输出格式
输出一行一个整数表示答案。
样例 #1
样例输入 #1
1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0
样例输出 #1
2200
数据规模与约定
对于全部的测试点，保证 $1 \leq n \leq 3.2 \times 10^4$，$1 \leq m \leq 60$，$0 \leq v_i \leq 10^4$，$1 \leq p_i \leq 5$，$0 \leq q_i \leq m$，答案不超过 $2 \times 10^5$。
- 给定的数据为离散数据，且只能使用一次
- 物品只有买与不买的选择，而且受到最大金额限制
- 求解目标是使总和（$$v_{j_k} \times w_{j_k}$$)最大
首先我们读题可以知道附件的必须跟随主件购买而且每个主件最多只有两个附件，所以我们可以将题目数划分为${ \text{主件}_1, \text{附件}_1, \text{附件}_2 },\quad { \text{主件}_2, \text{附件}_1, \text{附件}_2 },\quad \dots ,\quad { \text{主件}_n, \text{附件}_1, \text{附件}_2 }$。
于是我们每次进行决策时有以下情况
$$\text{选择：} \left{ \begin{aligned} &\text{购买主件} \quad \left{ \begin{aligned} &\text{购买附件 1} \quad \left{ \begin{aligned} &\text{购买附件 2} \ &\text{不购买附件 2} \end{aligned} \right. \ &\text{不购买附件 1}\quad\left{ \begin{aligned} &\text{购买附件 2} \ &\text{不购买附件 2} \end{aligned} \right. \end{aligned} \right. \ &\text{不购买主件} \end{aligned} \right.$$
我们秩序要将在每次作出是否购买主件的决策后再进行附件的购买决策即可
for (int i = 1; i < mainItemsValue.size(); i++) {
for (int j = budget; j >= mainItemsValue[i]; --j) {
if (j >= mainItemsValue[i]) dp[j] = max(dp[j], mainItemsWeight[i] + dp[j - mainItemsValue[i]]);
if (j >= mainItemsValue[i] + accessoryItemsValue[i][1]) dp[j] = max(dp[j], mainItemsWeight[i] +
accessoryItemsWeight[i][1] +
dp[j - mainItemsValue[i] - accessoryItemsValue[i][1]]);
if (j >= mainItemsValue[i] + accessoryItemsValue[i][2]) dp[j] = max(dp[j], mainItemsWeight[i] +
accessoryItemsWeight[i][2] +
dp[j - mainItemsValue[i] - accessoryItemsValue[i][2]]);
if (j >= mainItemsValue[i] + accessoryItemsValue[i][1] + accessoryItemsValue[i][2]) dp[j] = max(dp[j], mainItemsWeight[i] +
accessoryItemsWeight[i][1] +
accessoryItemsWeight[i][2] +
dp[j - mainItemsValue[i] -
accessoryItemsValue[i][1] -
accessoryItemsValue[i][2]]);
}
}
完整AC代码
int main(int argc, char *argv[]) {
int budget, numsOfItems;
vector<int> mainItemsValue(61);
vector<int> mainItemsWeight(61);
vector<vector<int>> accessoryItemsValue(61, vector<int>(3, 0));
vector<vector<int>> accessoryItemsWeight(61, vector<int>(3, 0));
cin >> budget >> numsOfItems;
vector<int> dp(budget+1, 0);
for (int i = 1; i <= numsOfItems; i++) {
int value, importance, itemType;
cin >> value >> importance >> itemType;
if (itemType == 0) {
mainItemsWeight[i] = importance * value;
mainItemsValue[i] = value;
}
else {
accessoryItemsValue[itemType][0]++;
int index = accessoryItemsValue[itemType][0];
accessoryItemsValue[itemType][index] = value;
accessoryItemsWeight[itemType][index] = importance * value;
}
}
for (int i = 1; i < mainItemsValue.size(); i++) {
for (int j = budget; j >= mainItemsValue[i]; --j) {
if (j >= mainItemsValue[i]) dp[j] = max(dp[j], mainItemsWeight[i] + dp[j - mainItemsValue[i]]);
if (j >= mainItemsValue[i] + accessoryItemsValue[i][1]) dp[j] = max(dp[j], mainItemsWeight[i] +
accessoryItemsWeight[i][1] +
dp[j - mainItemsValue[i] - accessoryItemsValue[i][1]]);
if (j >= mainItemsValue[i] + accessoryItemsValue[i][2]) dp[j] = max(dp[j], mainItemsWeight[i] +
accessoryItemsWeight[i][2] +
dp[j - mainItemsValue[i] - accessoryItemsValue[i][2]]);
if (j >= mainItemsValue[i] + accessoryItemsValue[i][1] + accessoryItemsValue[i][2]) dp[j] = max(dp[j], mainItemsWeight[i] +
accessoryItemsWeight[i][1] +
accessoryItemsWeight[i][2] +
dp[j - mainItemsValue[i] -
accessoryItemsValue[i][1] -
accessoryItemsValue[i][2]]);
}
}
cout << dp[budget] << endl;
}