动态规划+0-1背包问题

一、问题描述

小明周末要参加学校组织的跳蚤市场活动，他准备了足球、旱冰鞋、随身听和单词书四件物品进行交易，要用他的书包把这些物品带到学校。各物品的重量w和价值v如下图所示，小明书包的最大承重量为9（忽略单位），请你帮助他找到最合理的搭配方案，使他能用书包带到学校的物品价值最大。

二、问题解决

def find_all_max_value_combinations(weights, values, names, max_weight):  
    n = len(weights)
    all_best_combinations = []  # 用来存储所有最大价值的组合
    max_value = 0  

    def backtrack(index, current_weight, current_value, current_combination):  
        nonlocal max_value, all_best_combinations
        if index == n:  
            if current_weight <= max_weight and current_value > max_value:
                max_value = current_value
                all_best_combinations = [current_combination.copy()]#更新最大价值和对应的组合
            elif current_weight <= max_weight and current_value == max_value:
                all_best_combinations.append(current_combination.copy())#相同价值的组合也加入列表
            return  
        # 不选择当前物品
        backtrack(index + 1, current_weight, current_value, current_combination)  

        # 选择当前物品
        if current_weight + weights[index] <= max_weight:  
            current_combination.append(index)  
            backtrack(index + 1, current_weight + weights[index], current_value + values[index], current_combination)  
            current_combination.pop()  # 回溯时移除添加的物品索引

    # 初始调用回溯函数，寻找最大价值组合
    backtrack(0, 0, 0, [])
    return max_value, all_best_combinations

weights = [2, 4, 5, 3]  
values = [5, 4, 6, 2]  
names = ["足球", "旱冰鞋", "随身听", "单词书"]  
max_weight = 9  

max_value, all_best_combinations = find_all_max_value_combinations(weights, values, names, max_weight)  

print(f"最大价值为：{max_value}")
if all_best_combinations:  
    print("所有可能的最佳价值组合为：")
    for combination in all_best_combinations:
        print([names[i] for i in combination], "总重量:", sum(weights[i] for i in combination), 
              "对应价值:", sum(values[i] for i in combination))
else:
print("没有找到符合条件的组合。")

三·、思路分析

本程序实现了一个基于回溯算法来解决0-1背包问题，目的是找到在不超过背包最大承重的情况下，可携带物品的最大总价值。本程序首先计算出最大的价值，再寻找所有价值达到最大价值的组合，如果找到，则输出所有最佳价值组合，反之则给出没有符合条件的组合的提示。