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

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

  •  
  •   Oz2011 · 116 天前 · 550 次点击
    这是一个创建于 116 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

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

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

    你说的“完全有可能不从某组中拿东西啊”,而《背包九讲》中分组背包一节中提到“这个问题变成了每组物品有若干种策略:是选择本组的某一件,还是一件都不选。”可见你的问题已经被文档所涵盖。
        6
    Oz2011   112 天前
    @DaCong 对的,是分组背包,已经搞定啦,谢谢!
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   3778 人在线   最高记录 5043   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 28ms · UTC 01:13 · PVG 09:13 · LAX 17:13 · JFK 20:13
    ♥ Do have faith in what you're doing.