V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
ToPoGE
V2EX  ›  算法

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

  •  
  •   ToPoGE · 2021-12-07 16:51:38 +08:00 · 728 次点击
    这是一个创建于 842 天前的主题,其中的信息可能已经有所发展或是发生改变。
    有 8000 个{price:12,power:20}这样的数据,从里面取数据
    最多能拿 40 个数据,
    要求达到 4900 power ,且 price 最小,

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

    我好像找不到符合这个问题的背包模型
    有没有大佬能解一下
    ToPoGE
        1
    ToPoGE  
    OP
       2021-12-07 17:02:34 +08:00
    额外需求:
    要求获取到所有符合 power >= 4900 的数据
    RecursiveG
        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 的上限,不能就放宽。
    ToPoGE
        3
    ToPoGE  
    OP
       2021-12-19 16:10:04 +08:00
    @RecursiveG 大佬你这漏掉了前后组合情况,要找到最低价值的,

    我找网上大佬看了,这是个三维条件的 01 背包问题,已经解决了,
    感谢回复!
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3323 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 858ms · UTC 11:26 · PVG 19:26 · LAX 04:26 · JFK 07:26
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.