在Python中使用贪婪算法进行优化
在现实世界中，选择最佳选项是一个优化问题，因此，我们拥有最佳解决方案。在数学中，优化是一个非常广泛的主题，旨在找到最适合数据/问题的方法。可以使用贪婪算法（“贪婪算法是遵循解决问题的启发式算法，在每个阶段进行局部最优选择，以求找到全局最优值的算法”）来解决此类优化问题。这是Wikipedia的定义，我们通过牢记约束来找到最佳解决方案之一。这是用于优化的最简单算法之一。
让我们考虑一个问题，Hareus得到1500美元的零用钱。他是一个招待员，需要购买该月的必需品。因此，他保留了1000美元的必需品，现在剩下500美元中的其余部分用于他的支出。他去了超市，在那里他不得不根据买东西决定要买什么value(ameasureofeachitemrelatedtoproductivity)并且具有500$的约束。这是优化问题之一，以下是以最佳方式之一选择项目的代码。
关键思想：最高生产率为$500。
Python实现：
# 优化问题的贪婪算法
# 为物品定义了一个类，
# 其名称，价值和成本
class Itm(object):
def __init__(self, name, val, cost):
self.name= name
self.val= val
self.cost= cost
def getvalue(self):
return self.val
def getcost(self):
return self.cost
def __str__(self):
returnself.name
# 定义用于建立列表的功能
# 生成的项目列表
# 在超级市场有售
def buildlist(names, values, costs):
menu = []
for i in range(len(names)):
menu.append(Itm(names[i], values[i], costs[i]))
return menu
# 贪心算法的实现
# 选择最佳选择之一
def greedy(items, maxcal, keyfunction):
itemscopy = sorted(items, key = keyfunction, reverse = True)
result = []
totalval = 0
totalcal = 0
for i in range(len(items)):
if (totalcal + itemscopy[i].getcost() <= maxcal):
result.append(itemscopy[i])
totalval = totalval + itemscopy[i].getvalue()
totalcal = totalcal + itemscopy[i].getcost()
return (result, totalval)
# 主功能
# 所有值都是随机的
names = ['Ball', 'Gloves', 'Notebook', 'Bagpack', 'Charger', 'Pillow', 'Cakes', 'Pencil']
values = [89,90,95,100,90,79,50,10]
costs = [123,154,25,145,365,150,95,195]
Itemrs = buildlist(names, values, costs)
maxcost = 500 # 他必须花的最大钱
taken, totvalue = greedy(Itemrs, maxcost, Itm.getvalue)
print('Total vaule taken : ', totvalue)
# 打印选择的项目列表以获得最佳值
for i in range(len(taken)):
print(' ', taken[i])输出结果
Total vaule taken : 374 Bagpack Notebook Gloves Ball