0230903@163.com
# 2023年10月13日23:54:58
# version: 2.0
# python 3.7
# 经典递归
# 1. 装载物品
# 2. 装载物品，如果超重，就取下最重的
# 3. 装载物品，如果超重，就取下次重的
# 4. 依次类推
# 5. 最后，如果剩余物品的重量总和 <= 重量限制，那么就装载
# 6. 否则，不装载
class Knapsack:
def __init__(self, items, max_weight):
self.items = items
self.max_weight = max_weight
def get_max_value(self):
# 获取物品重量和价值
weight, value = self.get_weight_value()
# 计算可以装载的最大价值
max_value = self.get_max_value_with_weight_limitation(weight, value, self.max_weight)
return max_value
def get_weight_value(self):
weight = []
value = []
for item in self.items:
weight.append(item.get_weight())
value.append(item.get_value())
return weight, value
def get_max_value_with_weight_limitation(self, weight, value, weight_limit):
if not weight or not value or len(weight) != len(value) or weight_limit <= 0:
return 0
if len(weight) == 1:
if weight[0] <= weight_limit:
return value[0]
else:
return 0
if weight_limit - weight[0] < 0:
# 不能装入当前物品
return self.get_max_value_with_weight_limitation(weight[1:], value[1:], weight_limit)
else:
# 装入当前物品
max_value_with_weight = value[0] + self.get_max_value_with_weight_limitation(
weight[1:], value[1:], weight_limit - weight[0])
# 不装入当前物品
max_value_without_weight = self.get_max_value_with_weight_limitation(weight[1:], value[1:], weight_limit)
return max(max_value_with_weight, max_value_without_weight)
class Item:
def __init__(self, name, weight, value):
self.name = name
self.weight = weight
self.value = value
def get_weight(self):
return self.weight
def get_value(self):
return self.value
# 测试
if __name__ == '__main__':
items = [
Item("A", 10, 60),
Item("B", 20, 100),
Item("C", 30, 120)
]
max_weight = 50
knapsack = Knapsack(items, max_weight)
max_value = knapsack.get_max_value()
print("最大价值为:", max_value)