这是一个二维约束的 0/1 背包问题:每个朋友是一件物品,消耗时间 ti 与脑细胞 hi,价值为点赞数 ai;总时间不超过 T、总脑细胞不超过 H,问最大点赞数。
动态规划(二维 0/1 背包)
设 dp[t][h] 表示在时间上限为 t、脑细胞上限为 h 时能获得的最大点赞数。
对每个朋友进行一次倒序转移:
dp[t][h] = max(dp[t][h], dp[t - ti][h - hi] + ai) (t>=ti 且 h>=hi)
小朱同学看到小红书上有很多外国人涌入,于是决定给这些外国人展示他与朋友们的日常生活。
已知他有 n 个朋友,分享他第 i 个朋友的故事需要花费 Ti 的时间和 Hi 的脑细胞来编辑文章,并在发表后能获得 Ai 的点赞量。
请问:在花费总时间不超过 T 且总脑细胞不超过 H 的前提下,最多可以获得多少点赞量?
提示:1<=n<=100