题目：有N件物品和一个容量为V的背包。第i件物品的重量是w[i]，价值是v[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大
现在假设我们有七个物品，它们的重量为 35,30,60,50,40,10,25，价值分别为 10,40,30,50,35,40,30，背包的重大承重为150，装入一个或多个使其价值最大且不超过所能承受的重量？
思路1： 简单的贪婪 1)从剩余的物品中拿出价值最大并且状态为可以放置的物品（默认都是可以放置）
2) 检查包中是否还能容纳该物品的重量，如果能加放入包内，并且把该物品状态置为已放 置。如果重量超过包内还能容纳的重量则置物品状态为不能放置。
3) 重复以是步骤直到找不到可以放置的物品
代码：
先来一个表示物品信息类:
class Product(object):
weight = 0
values = 0
status = 0
def __init__(self, w, v, s):
super(Product, self).__init__()
self.weight = w
self.values = v
self.status = s
从物品中选出价值最大的 （状态0表示可放置， 1 表不已放置， 2表示不可放置）
def choose_by_price(objects):
index = -1
mp = 0
for j in range(0, len(objects)):
ob = objects[j]
if ob.status == 0 and mp < ob.values:
mp = ob.values
index = j
return index
解决背包问题：
def solve_package(objects, max_weight):
choose_products = []
total_weight = 0
#1)从剩余的物品中拿出价值最大并且状态为可以放置的物品
index = choose_by_price(objects)
choose_one = objects[index]
while index != -1:
print("index = %d" % index)
# 2)检查包中是否还能容纳该物品的重量，如果能加放入包内，并且把该物品状态置为已放 置
if objects[index].weight <= max_weight - total_weight:
print('weight = %d'% choose_one.weight)
objects[index].status = 1
choose_products.append(objects[index])
total_weight += objects[index].weight
#2)如果重量超过包内还能容纳的重量则置物品状态为不能放置
else:
objects[index].status = 2
#3) 重复以是步骤直到找不到可以放置的物品
index = choose_by_price(objects)
for product_one in choose_products:
print("%d\n" % product_one.weight)
经过上面的步骤我们能得到一个数值，但可能不是最优的，因为他只是简单的贪婪，还会有其它的方法比较更好的贪婪法来获取最优值。
如果我们以重量跟价值的比作为比较的标准情况会更好些，把上面的代码改一下：
__author__ = 'barryclass'
class Product(object):
status = 0
def __init__(self, value, weight, sta):
super(Product, self).__init__()
self.value_weight = value / weight
self.value = value
self.weight = weight
self.status = sta
def get_best_value_weight(products, weight):
have = False
choose = 0
for i in range(0, len(products)):
if products[i].status == 0 and products[i].value_weight >= products[choose].value_weight:
print('come here')
have = True
choose = i
if have:
return choose
return None
def solve_greedy_algorithm(products, weight):
left_weight = weight
result = []
index = get_best_value_weight(products, left_weight)
print(index)
while index is not None:
if products[index].weight <= left_weight:
result.append(products[index])
products[index].status = 1
left_weight -= products[index].weight
else:
products[index].status = 2
index = get_best_value_weight(products, left_weight)
return result
if __name__ == '__main__':
weights = [35.0, 30.0, 60.0, 50.0, 40.0, 10.0, 25.0]
value = [10, 40, 30, 50, 35, 40, 30]
products = []
for i in range(0, len(weights)):
product = Product(value[i], weights[i], 0)
products.append(product)
res = solve_greedy_algorithm(products, 150)
for product in res:
print(product.weight)
如果我们选择以价值最大来贪婪，获得物品重量 为50，10，30，40 其最大重量为 130 ，价值为 50， 40，40， 35 总价值为 165
如果是以价值重量比来贪婪, 获取物品重量为 10.0 30.0 25.0 50.0 35.0 价值为40 40 30 50 10 总价值为170