背包问题，贪心算法实现
2021-01-15 19:13
标签：背包问题 密度 while 条件 col static eth sdn 情况 背包问题：有 N 件物品和一个承重为 W 的背包（也可定义为体积），每件物品的重量是 weight，价值是 value，求解将哪几件物品装入背包可使这些物品在重量总和不超过 backpack_weight 的情况下价值总和最大。 这个问题隐含了一个条件，每个物品只有一件，也就是限定每件物品只能选择 0 个或 1 个，因此又被称为 0-1 背包问题。 weight_list = [2, 2, 6, 5, 4] value_list = [6, 3, 5, 4, 6] backpack_weight = 10 # 背包最大装10 针对这个问题，有三种贪婪策略的选择问题。 第一：根据最小重量贪心策略，这个策略每次选择最小重量的物品，最终选择装入背包的物品重量依次是 2， 2，4，5，6。 第二：根据最大价值贪心策略，这个策略每次都选择价值最大的物品，根据这个策略最终选择装入背包的物品价值依次是 6， 6， 5， 4， 3。 第三：根据取最大价值密度贪心策略，这个策略是定义一个价值密度的概念，每次选择都选价值密度最高的物品，物品的价值密度 s 定义为 value/weight。 该文参考链接：https://blog.csdn.net/zigzag_gy/article/details/102623839 背包问题，贪心算法实现 标签：背包问题 密度 while 条件 col static eth sdn 情况 原文地址：https://www.cnblogs.com/Gary1221/p/12934384.html
这里展示的是根据最小重量的贪心策略：class Goods:
def __init__(self, weight, value, status):
self.weight = weight
self.value = value
self.status = status # 0表示物品没有放入背包，1表示物品已放入背包
class Greedy(object):
def greedy(self, goods, weight): # goods表示物品的集合，weight表示背包的空闲重量
result_list = list()
sum_weight = 0
sum_value = 0
while True:
s = self.strategy(goods, weight)
if s == -1:
break
sum_weight = sum_weight + goods[s].weight
sum_value = sum_value + goods[s].value
new_dic = {"重量": goods[s].weight, "价值": goods[s].value}
result_list.append(new_dic)
weight = weight - goods[s].weight # 放入物品进去后，背包还剩余的空闲重量
goods[s].status = 1
goods.pop(s)
return result_list, sum_weight, sum_value
@staticmethod
def strategy(goods, weight):
index = -1
min_weight = goods[0].weight
for i in range(0, len(goods)):
current_goods = goods[i]
if current_goods.status == 0 and current_goods.weight and current_goods.weight min_weight:
index = i
weight = goods[index].weight
return index
if __name__ == ‘__main__‘:
goods_list = [Goods(2, 6, 0), Goods(2, 3, 0), Goods(6, 5, 0), Goods(5, 4, 0), Goods(4, 6, 0)]
g = Greedy()
result_data, total_weight, total_value = g.greedy(goods_list, 10)
print("--------------按照取最小重量贪心策略--------------")
print("最终的总重量为：" + str(total_weight))
print("最终的总价值为：" + str(total_value))
print("物品挑选为：", result_data)