博客

一、问题引入

一般的背包问题，背包仅有一个，如果背包多于一个，如何解决呢？

二、解决思路

根据动态规划的背包状态递推原理，我们可以自然地想到，如果背包多于一个，这只是在求最大效用时，最大项中多了一项，其它不变。对于此类问题，递归解决方案是最自然的方案。

三、解决方案

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)