一般的背包问题，背包仅有一个，如果背包多于一个，如何解决呢？
二、解决思路根据动态规划的背包状态递推原理，我们可以自然地想到，如果背包多于一个，这只是在求最大效用时，最大项中多了一项，其它不变。对于此类问题，递归解决方案是最自然的方案。
三、解决方案1、数据以python的字典形式保存，数据包括物品、阶段指标、阶段路径，物品字典的结构为：物品：(效用，重量)
2、数据做为参数，传入递归函数，
3、边界阶段值，在需要时，动态加入字典。
Knapsack_goods = {
"Tent": (10, 5),
"Moisture-proof mat": (7.5, 3.5),
"Punching jacket": (7, 2.5),
"Sleeping bag": (8, 4),
"Lifeline": (6, 4.5),
"mountaineering staff": (5, 2.5),
"Sun_protection_clothing": (5, 1.5),
"Water": (5.5, 3),
"Food": (3.5, 2),
"Fruits": (4, 2.5),
"Multi-purpose knife": (2, 0.75),
"Anti-mosquito oil": (1.0, 0.25),
"Hat": (1.0, 0.2),
"Towel": (1, 0.15),
"Headlamp": (2, 1),
"Fishing rod": (0.5, 1)
}
Target_indicators={}
Target_path={}
Target_path_vector={}
def get_Target_indicators(stages,
x_1_stages,
x_2_stages,
Knapsack_goods,
Target_indicators,
Target_path,
Target_path_vector):
if stages == len(Knapsack_goods) + 1:
Target_indicators[stages, x_1_stages, x_2_stages] = 0
Target_path[stages, x_1_stages, x_2_stages] = "Target"
Target_path_vector[stages, x_1_stages, x_2_stages] = []
if (stages, x_1_stages, x_2_stages) in Target_indicators:
return Target_indicators[stages, x_1_stages, x_2_stages], Target_path[stages, x_1_stages, x_2_stages],
Target_path_vector[stages, x_1_stages, x_2_stages]
else:
value = Knapsack_goods[list(Knapsack_goods.keys())[stages - 1]][0]
weight = Knapsack_goods[list(Knapsack_goods.keys())[stages - 1]][1]
optimal_paths_x1 = ""
optimal_paths_vector_x1 = ""
if x_1_stages >= weight:
optimal_values_x1, optimal_paths_x1, optimal_paths_vector_x1 = get_Target_indicators(
stages + 1, x_1_stages - weight, x_2_stages,
Knapsack_goods, Target_indicators, Target_path, Target_path_vector)
selected_indicators_x1 = value + optimal_values_x1
else:
selected_indicators_x1 = 0
optimal_paths_x2 = ""
optimal_paths_vector_x2 = ""
if x_2_stages >= weight:
optimal_values_x2, optimal_paths_x2, optimal_paths_vector_x2 = get_Target_indicators(
stages + 1, x_1_stages, x_2_stages - weight,
Knapsack_goods, Target_indicators, Target_path, Target_path_vector)
selected_indicators_x2 = value + optimal_values_x2
else:
selected_indicators_x2 = 0
optimal_values_n, optimal_paths_n, optimal_paths_vector_n = get_Target_indicators(
stages + 1, x_1_stages, x_2_stages, Knapsack_goods,
Target_indicators, Target_path, Target_path_vector)
Current_indicators = max(selected_indicators_x1, selected_indicators_x2, optimal_values_n)
if Current_indicators == selected_indicators_x1 and Current_indicators != 0:
optimal_paths = str(stages) + "_decision_select_into_1->" + optimal_paths_x1
optimal_paths_vector = [1] + optimal_paths_vector_x1
elif Current_indicators == selected_indicators_x2 and Current_indicators != 0:
optimal_paths = str(stages) + "_decision_select_into_2->" + optimal_paths_x2
optimal_paths_vector = [1] + optimal_paths_vector_x2
else:
optimal_paths = str(stages) + "_decision_no_select->" + optimal_paths_n
optimal_paths_vector = [0] + optimal_paths_vector_n
Target_indicators[stages, x_1_stages, x_2_stages] = Current_indicators
Target_path[stages, x_1_stages, x_2_stages] = optimal_paths
Target_path_vector[stages, x_1_stages, x_2_stages] = optimal_paths_vector
return Current_indicators, optimal_paths, optimal_paths_vector
Current_indicators, optimal_paths, optimal_paths_vector = get_Target_indicators(1, 8, 7, Knapsack_goods,
Target_indicators, Target_path, Target_path_vector)
print(Current_indicators)
print(optimal_paths)
print(optimal_paths_vector)
