Python ---- 算法入门(1)贪心算法解决部分背包问题
Python ---- 算法入门(1)贪心算法解决部分背包问题
Rattenking
发布于 2022-08-26 14:50:23
发布于 2022-08-26 14:50:23
文章被收录于专栏：Rattenking
1. 题目
假设商店中有 4 种商品，它们各自的重量和收益是：
- 商品 1：重量 20 斤，收益 100 元；
- 商品 2：重量 10 斤，收益 60 元；
- 商品 3：重量 40 斤，收益 100 元；
- 商品 4：重量 30 斤，收益 120 元；
对于每件商品，顾客可以购买商品的一部分（可再分）。一个小偷想到商店行窃，他的背包最多只能装 50 斤的商品，如何选择才能获得最大的收益呢？
2. 解决问题的思路【贪心算法】
- 贪心算法是每一步都追求最优的解决方案；
- 如何选择是最优的商品？【计算每个商品的收益率（收益/重量）】
- 使用贪心算法进行选择！【优先选择收益率最大的商品】
- 解决最终问题装够50斤！【直至所选商品的总重量达到 50 斤】
注意：虽然贪心算法每一步都是最优的解决方案，但整个算法并不一定是最优的。
3. 初始化背包大小和商品列表
# 背包可装总重量
w =50
# 所有商品信息列表
goods_info = [
{'name': 'goods1','weight': 20, 'profit': 100},
{'name': 'goods2','weight': 10, 'profit': 60},
{'name': 'goods3','weight': 40, 'profit': 100},
{'name': 'goods4','weight': 30, 'profit': 120},
]4. 计算各种商品的收益率
# 计算每个商品的收益率
def get_earning_rate(goods):
for item in goods:
rate = item['profit'] / item['weight']
item['rate'] = rate5. 比较收益率大小排序，最优商品到最差商品
# 对商品收益率排序【降序】，收益率从高到低
goods_info.sort(key=lambda a: a["rate"],reverse=True)6. 计算每种商品装的量和对应量的价值
# 计算每种商品装的量和对应量的价值
def get_goods_result_and_value(w, goods_info):
for item in goods_info:
current_goods_weight = item['weight']
current_weight = min(w, current_goods_weight)
result = current_weight / current_goods_weight
item['result'] = result
item['value'] = result * item['profit']
w = w - current_weight7. 输出每种商品的装入量
# 输出每种商品的装入量
def get_print_result(goods_info):
for item in goods_info:
result = item['result']
if result == 1:
print("总重量为 %.2f,总价值为 %.2f 的商品全部装入"%(item['weight'],item['profit']))
elif result == 0:
print("总重量为 %.2f,总价值为 %.2f 的商品不装"%(item['weight'],item['profit']))
else:
print("总重量为 %.2f,总价值为 %.2f 的商品装入%.2f%%"%(item['weight'],item['profit'],item['result']*100))8. 最终收获的商品价值
print("最终收获的商品价值为：%.2f" %(sum([item['value'] for item in goods_info])))9. 贪心算法解决部分背包问题的完整代码
'''
Descripttion:
version: 1.0.0
Author: Rattenking
Date: 2022-07-12 14:13:34
LastEditors: Rattenking
'''
# 计算每个商品的收益率
def get_earning_rate(goods):
for item in goods:
rate = item['profit'] / item['weight']
item['rate'] = rate
# 计算每种商品装的量和对应量的价值
def get_goods_result_and_value(w, goods_info):
for item in goods_info:
current_goods_weight = item['weight']
current_weight = min(w, current_goods_weight)
result = current_weight / current_goods_weight
item['result'] = result
item['value'] = result * item['profit']
w = w - current_weight
# 输出每种商品的装入量，返回价值列表
def get_print_result(goods_info):
for item in goods_info:
result = item['result']
if result == 1:
print("总重量为 %.2f,总价值为 %.2f 的商品全部装入"%(item['weight'],item['profit']))
elif result == 0:
print("总重量为 %.2f,总价值为 %.2f 的商品不装"%(item['weight'],item['profit']))
else:
print("总重量为 %.2f,总价值为 %.2f 的商品装入%.2f%%"%(item['weight'],item['profit'],item['result']*100))
if __name__ == '__main__':
# 背包可装总重量
w = 50
# 所有商品信息列表
goods_info = [
{'name': 'goods1','weight': 20, 'profit': 100},
{'name': 'goods2','weight': 10, 'profit': 60},
{'name': 'goods3','weight': 40, 'profit': 100},
{'name': 'goods4','weight': 30, 'profit': 120},
]
# 计算每个商品的收益率
get_earning_rate(goods_info)
# 对商品收益率排序【降序】，收益率从高到低
goods_info.sort(key=lambda a: a["rate"],reverse=True)
# 计算每种商品装的量和对应量的价值
get_goods_result_and_value(w, goods_info)
# 输出每种商品的装入量，返回价值列表
get_print_result(goods_info)
# 输出最终的商品获益价值
print("最终收获的商品价值为：%.2f" %(sum([item['value'] for item in goods_info])))10. 最终输出结果
在这里插入图片描述
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-07-12，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
