凑单算法

[JCZ2MkKb5S8ZX9pq]

• 假设有一个待购商品列表，价格写入一个数组[58,128,98,32]等等（长度价格随意），或者是一个字典。
• 假设 199 包邮。
• 购买商品必须为整数，可以为 0。
• 目标是凑到商品总价>199 且最低时，商品的数量组合。

---

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

[cookii]

看起来是 [背包问题] 吧

[geelaw]

这是一个背包问题，一般化后的决定版本是 NP 困难的。

[JCZ2MkKb5S8ZX9pq]

@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]