動(dòng)態(tài)規(guī)劃之01背包問題及改進(jìn)-文庫(kù)吧
2025-07-07 00:49 本頁面
【正文】 3 4 5 背包容量0~capacity,不是0~capacity1 6 def knapsack(weight, value, capacity): 7 if len(weight) != len(value): 8 print(parameter err!) 9 return10 obj_num = len(weight)11 result = [[] for x in range(obj_num)]12 divide = min(weight[1], capacity)13 result[1] = [0 for x in range(divide)]14 result[1].extend(value[1] for x in range(divide, capacity + 1))15 for i in reversed(list(range(1, obj_num 1))):16 divide = min(weight[i], capacity)17 for j in range(divide):18 result[i].append(result[i + 1][j])19 for j in range(divide, capacity + 1):20 result[i].append(max(result[i + 1][j], result[i + 1][j weight[i]] + value[i]))21 22 result[0] = {capacity: result[1][capacity]}23 if weight[0] = capacity:24 result[0][capacity] = max(result[1][capacity], result[1][capacity weight[0]] + value[0])25 26 vector = [0 for x in range(obj_num)]27 capacity_temp = capacity28 for i in range(obj_num 1):29 if result[i][capacity_temp] != result[i + 1][capacity_temp]:30 vector[i] = 131 capacit
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號(hào)-1