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

V 友们,问个算法题啦哈哈

  •  
  •   Oz2011 · 2019-07-25 19:59:49 +08:00 · 2495 次点击
    这是一个创建于 1708 天前的主题,其中的信息可能已经有所发展或是发生改变。

    一共 20 个种类的物品,每个种类有 10 件,每件都有价格,运费,评分 (价格在 1-20 之间,运费在 2-5 之间)

    问,每个总类最多拿一件物品,要求在价格+运费<=50 的情况下 使得评分之和最高

    6 条回复    2019-07-30 09:00:08 +08:00
    newtype0092
        1
    newtype0092  
       2019-07-25 20:42:56 +08:00
    搜《背包九讲》,一次解决所有相关问题。你这个应该属于里面的“分组背包”问题。
    litmxs
        2
    litmxs  
       2019-07-25 20:43:52 +08:00 via Android
    背包
    jmc891205
        3
    jmc891205  
       2019-07-25 20:46:04 +08:00 via iPhone
    每种最多只能拿 1 件的话
    每种有 10 件这个条件好像没啥用
    Oz2011
        4
    Oz2011  
    OP
       2019-07-26 05:24:03 +08:00 via iPhone
    @newtype0092 可问题是,完全有可能不从某组中拿东西啊
    DaCong
        5
    DaCong  
       2019-07-26 21:06:17 +08:00   ❤️ 1
    同 1 楼,这个问题已经被《背包九讲》讨论过,这里给出链接 https://github.com/tianyicui/pack/blob/master/V2.pdf
    请看其中的分组背包一节。

    你说的“完全有可能不从某组中拿东西啊”,而《背包九讲》中分组背包一节中提到“这个问题变成了每组物品有若干种策略:是选择本组的某一件,还是一件都不选。”可见你的问题已经被文档所涵盖。
    Oz2011
        6
    Oz2011  
    OP
       2019-07-30 09:00:08 +08:00
    @DaCong 对的,是分组背包,已经搞定啦,谢谢!
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   992 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 30ms · UTC 20:05 · PVG 04:05 · LAX 13:05 · JFK 16:05
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.