Python ---- 算法入门(1)贪心算法解决部分背包问题

假设商店中有 4 种商品，它们各自的重量和收益是：

1. 商品 1：重量 20 斤，收益 100 元；
2. 商品 2：重量 10 斤，收益 60 元；
3. 商品 3：重量 40 斤，收益 100 元；
4. 商品 4：重量 30 斤，收益 120 元；

对于每件商品，顾客可以购买商品的一部分（可再分）。一个小偷想到商店行窃，他的背包最多只能装 50 斤的商品，如何选择才能获得最大的收益呢？

1. 贪心算法是每一步都追求最优的解决方案；
2. 如何选择是最优的商品？【计算每个商品的收益率（收益/重量）】
3. 使用贪心算法进行选择！【优先选择收益率最大的商品】
4. 解决最终问题装够50斤！【直至所选商品的总重量达到 50 斤】

注意：虽然贪心算法每一步都是最优的解决方案，但整个算法并不一定是最优的。

# 背包可装总重量
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},
  ]

# 计算每个商品的收益率
def get_earning_rate(goods):
  for item in goods:
    rate = item['profit'] / item['weight']
    item['rate'] = rate

# 对商品收益率排序【降序】，收益率从高到低
goods_info.sort(key=lambda a: a["rate"],reverse=True)

# 计算每种商品装的量和对应量的价值
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))

print("最终收获的商品价值为：%.2f" %(sum([item['value'] for item in goods_info])))

'''
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])))

我的博客，欢迎交流！

我的CSDN博客，欢迎交流！

微信小程序专栏

前端笔记专栏

微信小程序实现部分高德地图功能的DEMO下载

微信小程序实现MUI的部分效果的DEMO下载

微信小程序实现MUI的GIT项目地址

微信小程序实例列表

前端笔记列表

游戏列表