def multi_dimensional_knapsack(items, limits):
    """
    多维度背包问题解决方案
    """
    n = len(items)  # 物品数量
    dimensions = len(limits)  # 维度数量

    # 1. 创建多维dp数组
    dp = {}
    # 初始化：加入零状态
    dp[tuple([0] * dimensions)] = 0  # 添加这一行来处理初始状态

    def get_dp_value(state):
        """获取dp值，不存在则返回0"""
        return dp.get(state, 0)

    # 2. 实现状态转移
    for i in range(n):  # 遍历每个物品
        new_states = {}

        # 获取当前物品的各维度值
        current_item = items[i]
        item_values = [
            current_item['energy'],
            current_item['protein'],
            current_item['potassium'],
            current_item['phosphorus'],
            current_item['sodium'],
            current_item['liquid']
        ]

        # 遍历当前已存在的所有状态
        current_states = list(dp.items())  # 转换为列表避免运行时修改字典
        for state, value in current_states:
            # 检查加入当前物品是否超出限制
            can_add = True
            new_state = []
            for dim in range(dimensions):
                new_value = state[dim] + item_values[dim]
                if new_value > limits[dim]:
                    can_add = False
                    break
                new_state.append(new_value)

            if can_add:
                new_state_tuple = tuple(new_state)
                # 更新状态：选择当前物品
                new_value = value + current_item['value']
                if new_value > get_dp_value(new_state_tuple):
                    new_states[new_state_tuple] = new_value

        # 将新状态合并到dp中
        dp.update(new_states)

    # 如果dp为空，说明没有可行解
    if not dp:
        return []

    # 3. 回溯找出选择的物品
    selected_items = []
    # 找出价值最大的可行状态
    max_value = -1
    best_state = None
    for state, value in dp.items():
        if value > max_value:
            max_value = value
            best_state = state

    if best_state is None:
        return []

    # 回溯过程
    current_state = best_state
    remaining_value = dp[current_state]

    for i in range(n - 1, -1, -1):
        item = items[i]
        item_values = [
            item['energy'],
            item['protein'],
            item['potassium'],
            item['phosphorus'],
            item['sodium'],
            item['liquid']
        ]

        # 检查是否选择了当前物品
        previous_state = []
        for dim in range(dimensions):
            previous_state.append(current_state[dim] - item_values[dim])

        previous_state_tuple = tuple(previous_state)
        if (all(v >= 0 for v in previous_state) and
                get_dp_value(previous_state_tuple) == remaining_value - item['value']):
            selected_items.append(item)
            current_state = previous_state_tuple
            remaining_value = dp[current_state]

    return selected_items


# 测试
if __name__ == '__main__':
    items = [
        {
            'name': '鸡蛋',
            'energy': 70,  # 70千卡
            'protein': 6,  # 6克蛋白质
            'potassium': 100,  # 100毫克钾
            'phosphorus': 80,  # 80毫克磷
            'sodium': 70,  # 70毫克钠
            'liquid': 0,  # 0毫升液体
            'value': 5  # 价值评分
        },
        {
            'name': '牛奶',
            'energy': 120,  # 120千卡
            'protein': 8,  # 8克蛋白质
            'potassium': 150,  # 150毫克钾
            'phosphorus': 90,  # 90毫克磷
            'sodium': 50,  # 50毫克钠
            'liquid': 200,  # 200毫升液体
            'value': 4  # 价值评分
        },
        {
            'name': '鸡胸肉',
            'energy': 165,  # 165千卡
            'protein': 31,  # 31克蛋白质
            'potassium': 250,  # 250毫克钾
            'phosphorus': 200,  # 200毫克磷
            'sodium': 75,  # 75毫克钠
            'liquid': 0,  # 0毫升液体
            'value': 8  # 价值评分
        },
        {
            'name': '全麦面包',
            'energy': 150,  # 150千卡
            'protein': 4,  # 4克蛋白质
            'potassium': 80,  # 80毫克钾
            'phosphorus': 60,  # 60毫克磷
            'sodium': 180,  # 180毫克钠
            'liquid': 0,  # 0毫升液体
            'value': 3  # 价值评分
        },
        {
            'name': '香蕉',
            'energy': 90,  # 90千卡
            'protein': 1,  # 1克蛋白质
            'potassium': 350,  # 350毫克钾
            'phosphorus': 20,  # 20毫克磷
            'sodium': 1,  # 1毫克钠
            'liquid': 0,  # 0毫升液体
            'value': 2  # 价值评分
        }
    ]

    limits = [
        1500,  # 能量上限（千卡）
        15,  # 蛋白质上限（克）
        2000,  # 钾上限（毫克）
        800,  # 磷上限（毫克）
        2300,  # 钠上限（毫克）
        1500  # 液体上限（毫升）
    ]

    result = multi_dimensional_knapsack(items, limits)

    # 打印结果
    print("选择的食物：")
    total_values = [0] * len(limits)
    total_value = 0
    for item in result:
        print(f"- {item['name']}")
        total_values[0] += item['energy']
        total_values[1] += item['protein']
        total_values[2] += item['potassium']
        total_values[3] += item['phosphorus']
        total_values[4] += item['sodium']
        total_values[5] += item['liquid']
        total_value += item['value']

    print("\n总计：")
    print(f"能量: {total_values[0]}/{limits[0]} 千卡")
    print(f"蛋白质: {total_values[1]}/{limits[1]} 克")
    print(f"钾: {total_values[2]}/{limits[2]} 毫克")
    print(f"磷: {total_values[3]}/{limits[3]} 毫克")
    print(f"钠: {total_values[4]}/{limits[4]} 毫克")
    print(f"液体: {total_values[5]}/{limits[5]} 毫升")
    print(f"总价值: {total_value}")