凑单算法 - V2EX

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 2447 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

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

商品

假设

字典

写入

3 条回复

cookii

2019 年 8 月 13 日

看起来是 [背包问题] 吧

geelaw

2019 年 8 月 13 日 via iPhone

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

JCZ2MkKb5S8ZX9pq

2019 年 8 月 13 日

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