背包算法——双条件背包

通过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]);

感悟：

1. 这里的k，也就是事件，等价于背包问题中的物品；对于背包问题来说，只对物品的体积（重量）这一个指标进行限制，这里的精力与体力就相当于背包问题中的体积，相当于两个限制。
2. 之所以不管01背包还是完全背包，都可以把dp数组初始化为一维而不是二维，就是因为省略了第一维的物品数量；这里我们dp数组初始化为二维，但是最外层进行k次迭代，也就相当于省略了事件数量。
3. 基于上面的理解，为什么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数据的正确性。
4. plus，如果修改题目，没件事情可以重复分享，那么就正序计算dp[i][j]，按照上面的测例算出来结果是8，完全没问题。

如果以前没接触过背包问题，这篇文章确实p用没有，但是如果正对背包问题处于似懂非懂的状态，或许看下对你有所帮助，加油。

这篇好文章是转载于：学新通技术网