刚好买东西想到这么个问题,各位有啥思路嘛?
1
cookii 2019-08-13 16:31:23 +08:00
看起来是 [背包问题] 吧
|
2
geelaw 2019-08-13 16:38:09 +08:00 via iPhone
这是一个背包问题,一般化后的决定版本是 NP 困难的。
|
3
JCZ2MkKb5S8ZX9pq OP @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] |