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

凑单算法

  •  
  •   JCZ2MkKb5S8ZX9pq · 2019-08-13 14:41:43 +08:00 · 2984 次点击
    这是一个创建于 1689 天前的主题,其中的信息可能已经有所发展或是发生改变。
    • 假设有一个待购商品列表,价格写入一个数组[58,128,98,32]等等(长度价格随意),或者是一个字典。
    • 假设 199 包邮。
    • 购买商品必须为整数,可以为 0。
    • 目标是凑到商品总价>199 且最低时,商品的数量组合。

    刚好买东西想到这么个问题,各位有啥思路嘛?

    imzhoukunqiang
        1
    imzhoukunqiang  
       2019-08-13 16:31:23 +08:00
    看起来是 [背包问题] 吧
    geelaw
        2
    geelaw  
       2019-08-13 16:38:09 +08:00 via iPhone
    这是一个背包问题,一般化后的决定版本是 NP 困难的。
    JCZ2MkKb5S8ZX9pq
        3
    JCZ2MkKb5S8ZX9pq  
    OP
       2019-08-13 16:44:10 +08:00
    @imzhoukunqiang
    @geelaw
    不懂啥是背包问题,凑合写了一个,基本满足我自己的需求了。
    缩进随缘吧。有空改个 js 的挂网页。

    item = {'creatine': 64.35, 'protein': 103.35, 'bcaa': 64.35}
    priceLimit = 428

    # 格式化商品数据
    itemDict = {}
    for name, price in item.items():
    itemDict.setdefault(price, '')
    itemDict[price] += f'/{name}'
    itemDict[price] = itemDict[price].lstrip('/')
    itemList = sorted(itemDict.items(), key=lambda x: x[1])
    drawTitle('ITEMLIST')
    [print(f'{price:8.2f} | {name}') for price, name in itemList]
    print(f'\nTraget Price: {priceLimit:.2f}')
    r = {}


    def orderNum(itemList, prevOrder='', prevPrice=0):
    for num in range(999):
    price, name = itemList[0]
    thisOrder = f'{prevOrder} + {num} {name}' if num else ''
    thisPrice = prevPrice + price * num

    # 如果当前价格超了 就不再增加数量
    if thisPrice >= priceLimit:
    r[thisOrder.strip('+ ')] = thisPrice
    return

    # 如果价格没超 就往下一位
    if len(itemList) > 1:
    orderNum(itemList[1:], thisOrder, thisPrice)


    orderNum(itemList)
    # 按总价升序
    r = sorted(r.items(), key=lambda d: d[1])
    drawTitle('RESULT')
    [print(f'{total:>8.2f} | {order}') for order, total in r]
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3913 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 05:10 · PVG 13:10 · LAX 22:10 · JFK 01:10
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.