提供了Python编程的基础技术教程

Python程序教程

您现在的位置是：首页 >  python入门

当前栏目

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

算法,Python,----,入门,贪心,解决,部分,背包,问题
2025-03-25 08:59:26 时间

1. 题目

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

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

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

2. 解决问题的思路【贪心算法】

  1. 贪心算法是每一步都追求最优的解决方案；
  2. 如何选择是最优的商品？【计算每个商品的收益率（收益/重量）】
  3. 使用贪心算法进行选择！【优先选择收益率最大的商品】
  4. 解决最终问题装够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'] = rate

5. 比较收益率大小排序，最优商品到最差商品

# 对商品收益率排序【降序】，收益率从高到低
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_weight

7. 输出每种商品的装入量

# 输出每种商品的装入量
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. 最终输出结果

相关文章