求解一个类似又不类似的背包问题

2021-12-07 16:51:38 +08:00
 ToPoGE
有 8000 个{price:12,power:20}这样的数据,从里面取数据
最多能拿 40 个数据,
要求达到 4900 power ,且 price 最小,

有个限制可以有,也可以没有,power 上限 200 ,最低 50 ,price 任意

我好像找不到符合这个问题的背包模型
有没有大佬能解一下
914 次点击
所在节点    算法
3 条回复
ToPoGE
2021-12-07 17:02:34 +08:00
额外需求:
要求获取到所有符合 power >= 4900 的数据
RecursiveG
2021-12-19 15:30:08 +08:00
先取 power 最大的几个看能不能超过 4900 ,然后计算总 price ,这是 price 的上限,记作 P_MAX 。然后二分查询 0 到 P_MAX ,问在 price 的和不超过 P_MAX/2 ,总数不超过 40 的情况下能取得的最大 power 是多少,如果能到 4900 就继续收紧 price 的上限,不能就放宽。
ToPoGE
2021-12-19 16:10:04 +08:00
@RecursiveG 大佬你这漏掉了前后组合情况,要找到最低价值的,

我找网上大佬看了,这是个三维条件的 01 背包问题,已经解决了,
感谢回复!

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/820664

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX