算法-购物车问题
问题描述
终于发了年终奖准备去网上购物，如何能在有限的预算内，得到最大的收益呢。如果只到这里的话，其实就是一个背包问题，可以参考链接。
然鹅还有其他条件：
可以购买的物品分为两类：主物品可以单独购买，附件物品只能在已经购买了主物品的情况下购买。例如，要购买打印机，需要先购买电脑。另外，一个主件商品，最多有2个附件商品。
计算满意度=物品价格*物品重要性
其实还有一个默认条件，那就是每个物品默认只购买一次。想想也很合理，又不是消耗品，多买只会降低边际效应。
问题抽象
用代码来抽象表示，大概如下这样
# 总预算1000，可选商品数量5个
m = 1000
n = 5
物品价格和重要性，以及主附关系如下：（题目还有个提示是，价格都是10的倍数
# 价格 重要性 主件还是附件，1说明他们是第一件物品的附件
goods = [
[800, 2, 0],
[400, 5, 1],
[300, 5, 1],
[400, 3, 0],
[500, 2, 0]
]
问题分解
因为最终考虑的是商品的满意度，也就是计算价格*重要度，所以先对商品数据做处理
def get_value(price, point):
"""计算价格和满意度"""
value_ = [price, price*point]
return value_
- 每次考虑是否购入一种商品时，因为附件至多有2个，有以下4种情况：
- 只购买主件
- 购买主件+附件1
- 购买主件+附件2
- 购买主件+附件1+附件2
def work(key, value, attachments):
"""模拟4种情况"""
prices, points = [], []
# 1.仅有主件
prices.append(value[0])
points.append(value[1])
if key in attachments:
# 2. 主件 + 附件1
prices.append(prices[0] + attachments[key][0][0])
points.append(points[0] + attachments[key][0][1])
if len(attachments[key]) == 2:
# 3.主件+附件2
prices.append(prices[0] + attachments[key][1][0])
points.append(prices[0] + attachments[key][1][1])
# 4.主件+ 附件1 + 附件2
prices.append(prices[0] + attachments[key][0][0] + attachments[key][1][0])
points.append(points[0] + attachments[key][0][1] + attachments[key][1][1])
return prices, points
用2个字典分别存储主件和附件，一个res列表存储最优解
# 主件 附件 结果列表
main_goods, attachments, res_list = {}, {}, [0] *(m+1)
- 遍历商品，将主件和附件，分别添加进字典
for i in range(n):
price, point, att = goods[i][0], goods[i][1], goods[i][2]
# 把商品简化成价格 和 满意度
good = get_value(price, point)
# 如果是主件
if att == 0:
# 添加进主件字典, 注意i+1，这样就和附件的主件对应上了
main_goods[i+1] = good
# 如果是附件
else:
# 如果该附件编号key已经存在了
if att in attachments:
# 这个key下的列表，加上该附件商品
attachments[att].append(good)
# 不存在就创建这个key
else:
attachments[att] = [good]
- 最终，对主件商品进行遍历，计算每个预算的结果，这里类似于背包问题里一行内的值计算
# 对主件字典进行遍历
for key, value in main_goods.items():
# prices列表和points列表，分别计算了4种情况的价格和满意度
prices, points = work(key, value, attachments)
# 对一列的所有值进行遍历
for j in range(m, -1, -10): # 价格是10的倍数
# 判断价格是否在预算内
for k in range(len(prices)):
# 如果在预算内
if j - prices[k] >= 0:
# 最优解在 上一次的最优解 和 剩余预算的最优解+当前满意度 之间取大的那个
res_list[j] = max(res_list[j], res_list[j-prices[k]] + points[k])
最后返回结果，
return res_list[m]
完整代码如下
def get_value(price, point):
"""计算价格和满意度"""
value_ = [price, price*point]
return value_
def work(key, value, attachments):
"""模拟4种情况"""
prices, points = [], []
# 1.仅有主件
prices.append(value[0])
points.append(value[1])
if key in attachments:
# 2. 主件 + 附件1
prices.append(prices[0] + attachments[key][0][0])
points.append(points[0] + attachments[key][0][1])
if len(attachments[key]) == 2:
# 3.主件+附件2
prices.append(prices[0] + attachments[key][1][0])
points.append(prices[0] + attachments[key][1][1])
# 4.主件+ 附件1 + 附件2
prices.append(prices[0] + attachments[key][0][0] + attachments[key][1][0])
points.append(points[0] + attachments[key][0][1] + attachments[key][1][1])
return prices, points
def main():
# 总预算1000， 可选商品5
m, n = 1000, 5
# 商品的价格 重要度 是否附件
goods = [
[800, 2, 0],
[400, 5, 1],
[300, 5, 1],
[400, 3, 0],
[500, 2, 0]
]
# 主件 附件
main_goods, attachments, res_list = {}, {}, [0] * (m+1)
for i in range(n):
price, point, att = goods[i][0], goods[i][1], goods[i][2]
# 把商品简化成价格 和 满意度
good = get_value(price, point)
# 如果是主件
if att == 0:
# 添加进主件字典
main_goods[i+1] = good
# 如果是附件
else:
# 如果该附件编号key已经存在了
if att in attachments:
# 这个key下的列表，加上该附件商品
attachments[att].append(good)
# 不存在就创建这个key
else:
attachments[att] = [good]
# 对主件字典进行遍历
for key, value in main_goods.items():
# prices列表和points列表，分别计算了4种情况的价格和满意度
prices, points = work(key, value, attachments)
# 对一列的所有值进行遍历
for j in range(m, -1, -10): # 价格是10的倍数
# 判断价格是否在预算内
for k in range(len(prices)):
# 如果在预算内
if j - prices[k] >= 0:
# 最优解在 上一次的最优解 和 剩余预算的最优解+当前满意度 之间取大的那个
res_list[j] = max(res_list[j], res_list[j-prices[k]] + points[k])
print(res_list)
return res_list[m]
if __name__ == '__main__':
print(main())
参考了如下链接：https://blog.csdn.net/kk_gods/article/details/116048116
标签：attachments,购物车,问题,附件,算法,points,key,prices,主件 From： https://blog.csdn.net/kayotin/article/details/136887700