这是一个创建于 1929 天前的主题，其中的信息可能已经有所发展或是发生改变。
- 假设有一个待购商品列表，价格写入一个数组[58,128,98,32]等等（长度价格随意），或者是一个字典。
- 假设 199 包邮。
- 购买商品必须为整数，可以为 0。
- 目标是凑到商品总价>199 且最低时，商品的数量组合。
刚好买东西想到这么个问题，各位有啥思路嘛？
 |
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] |
Select Language