这是一个二维约束的 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。他希望在总花费时间不超过 T 且总消耗脑细胞不超过 H 的条件下,选择一部分朋友的故事进行分享,使得获得的点赞总数尽可能大。
请你求出小明能够获得的最大点赞总数。
约束条件:
© CodeFun2000 · 使用条款
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册