背包算法——双条件背包
通过8.6日的小红书笔试第二题,我彻底搞懂了01背包与完全背包。
这篇文章不是手把手的基础教学,简单从我自己的对背包问题掌握的基础上分享一下新的心得,随缘帮助陌生人。
题目:
小红很喜欢前往小红书分享她的日常生活。已知她生活中有n个事件,分享第i个事件需要她花费ti的时间和hi的精力来编辑文章,并能获得ai的快乐值。
小红想知道,在总花费时间不超过T且总花费精力不超过H的前提下,小红最多可以获得多少快乐值?
第一行输入一个正整数n,代表事件的数量。
第二行输入两个正整数T和H,代表时间限制和精力限制。
接下来的n行,每行输入三个正整数ti,hi,ai,代表分享第i个事件需要花费ti的时间、hi的精力,收获ai的快乐值。
输入示例:
3
5 4
1 2 2
2 1 3
4 1 5
输出示例:
7
考场上的做法——暴力递归(超时,通过36%)
下面的一段没啥好说的,输入数据的处理:
const n = parseInt(read_line());
const tArr = new Array(n).fill();
const hArr = new Array(n).fill();
const aArr = new Array(n).fill();
let line2 = read_line();
const T = parseInt(line2.split(" ")[0]);
const H = parseInt(line2.split(" ")[1]);
// 构造t\h\a数组
for(let i = 0; i < n; i ++) {
let line = read_line().split(" ");
line = line.map((str) => {
return parseInt((str));
})
tArr[i] = line[0];
hArr[i] = line[1];
aArr[i] = line[2];
}
最终处理的目标是如下的数据结构:
// 输入:
// 3
// 5 4
// 1 2 2
// 2 1 3
// 4 1 5
let n = 3;
const T = 5;
const H = 4;
const tArr = [1, 2, 4];
const hArr = [2, 1, 1];
const aArr = [2, 3, 5];
递归算法部分,没啥好说的,下面是笔试时的源代码:
let maxA = 0; // 最大快乐值
// 考察第i件事情,并且考察前的t, h, a值分别为t, h, a
function backTrace(i, t, h, a) {
if(a > maxA) {
maxA = a;
}
if(i === n) return;
backTrace(i + 1, t, h, a); // 不做第i件事
if(t + tArr[i] <= T && h + hArr[i] <= H) { // 做第i件事
backTrace(i + 1, t + tArr[i], h + hArr[i], a + aArr[i]);
}
}
backTrace(0, 0, 0, 0);
console.log(maxA);
dp动态规划
数据读取同上,dp算法部分:
let dp = new Array(T + 1).fill(); // 定义dp[i][j]表示i的精力与j的体力能获得的最大快乐值
dp = dp.map(() => {
return new Array(H + 1).fill(0);
})
for(let k = 0; k < n; k ++) { // k表示下面计算dp[i][j]时事件的集合是前k件事情
for(let i = 1; i <= T; i ++) { // i, j 遍历各种时间和精力组合,计算dp[i][j],注意必须是倒序遍历i\j!!!
for(let j = 1; j <= H; j ++) {
if(i >= tArr[k] && j >= hArr[k]) {
dp[i][j] = Math.max(dp[i - tArr[k]][j - hArr[k]] + aArr[k], dp[i][j]);
}
}
}
}
// 打印dp数组
for(let i = 0; i <= T; i ++) {
let str = '';
for(let j = 0; j <= H; j ++) {
str += dp[i][j];
str += " ";
}
console.log(str);
}
console.log(dp[T][H]);
感悟:
- 这里的k,也就是事件,等价于背包问题中的物品;对于背包问题来说,只对物品的体积(重量)这一个指标进行限制,这里的精力与体力就相当于背包问题中的体积,相当于两个限制。
- 之所以不管01背包还是完全背包,都可以把dp数组初始化为一维而不是二维,就是因为省略了第一维的物品数量;这里我们dp数组初始化为二维,但是最外层进行k次迭代,也就相当于省略了事件数量。
- 基于上面的理解,为什么i和j都要倒序遍历就显而易见了,因为本题显然对标01背包问题,也就是说每件事情最多分享一次,所以说如果不省略第一维度k的递推公式应该是:
dp[k][i][j] = max(dp[k - 1][i][j], dp[k - 1][i - tArr[k]][j - hArr[k]]) + aArr[k]
。说白了就是**dp[k] = f(dp[k - 1])
** ,所以因为我们省略了第一维k,完全等价于背包问题省略第一维,所以需要倒序计算,可以类比01背包问题的一维dp数组,倒序的目的就是保证计算dp[j]时所使用的dp数据的正确性。 - plus,如果修改题目,没件事情可以重复分享,那么就正序计算
dp[i][j]
,按照上面的测例算出来结果是8,完全没问题。
如果以前没接触过背包问题,这篇文章确实p用没有,但是如果正对背包问题处于似懂非懂的状态,或许看下
作者:荣达
来源:juejin.cn/post/7264792741951062068
对你有所帮助,加油。来源:juejin.cn/post/7264792741951062068