这是一个创建于 1080 天前的主题，其中的信息可能已经有所发展或是发生改变。
有 8000 个{price:12,power:20}这样的数据，从里面取数据
最多能拿 40 个数据，
要求达到 4900 power ，且 price 最小，
有个限制可以有，也可以没有，power 上限 200 ，最低 50 ，price 任意
我好像找不到符合这个问题的背包模型
有没有大佬能解一下
最多能拿 40 个数据，
要求达到 4900 power ，且 price 最小，
有个限制可以有，也可以没有，power 上限 200 ，最低 50 ，price 任意
我好像找不到符合这个问题的背包模型
有没有大佬能解一下
 |
1
ToPoGE OP 额外需求：
要求获取到所有符合 power >= 4900 的数据 |
 |
2
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 的上限，不能就放宽。
|
|
3
ToPoGE OP |
Select Language