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

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

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

    一共 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   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   2019-07-30 09:00:08 +08:00
    @DaCong 对的,是分组背包,已经搞定啦,谢谢!
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2859 人在线   最高记录 5168   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 36ms · UTC 13:28 · PVG 21:28 · LAX 06:28 · JFK 09:28
    ♥ Do have faith in what you're doing.