用穷举法解决搬砖问题代码

搬砖问题是经典的组合优化问题，通常涉及将一定数量的砖块从源点搬运到目标点，每一块砖有固定的重量和价值，每移动一次需要一定的费用。使用穷举法（也称为暴力搜索或枚举法）来求解这种问题的一个基本思路是：

1. 定义变量：比如`weights`存储砖块的重量，`values`存储砖块的价值，`costs`表示搬运费用，`source`和`destination`代表起始点和终点。

2. 创建所有可能的搬运方案：对于每个砖块，都有两种选择——携带或不携带。这可以用一个二进制数组或列表来表示，例如`carryPlans`，长度等于砖块的数量。

3. 枚举所有可能的携带模式：遍历这个列表，计算每种模式下的总价值、总重量和总费用。

4. 计算收益：如果总价值减去总费用大于0，则该方案是可行的，记录下来或者比较当前的最大收益。

5. 重复步骤3和4直到穷举所有可能。

6. 返回最优方案：找到所有可能方案中收益最大的那一种。

由于穷举法的时间复杂度是O(2^n)，其中n是砖块数量，当砖块数量较大时，这种方法效率低下，不适合实际应用。更常见的做法是使用动态规划或贪心算法来优化。

def move_bricks(weights, values, costs, source, destination):
    n = len(weights)
    max_profit = float('-inf')
    best_plan = []

    # 初始化状态数组
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    
    # 动态规划核心部分
    for i in range(1, n + 1):
        for j in range(i, n + 1):
            if weights[i - 1] <= j:  # 如果第i个砖能装进前j个位置
                dp[j][i] = max(dp[j][i], dp[j - weights[i - 1]][i - 1] + values[i - 1])  # 取值最大
                if dp[j][i] > max_profit:
                    max_profit = dp[j][i]
                    best_plan = [0] * (i - 1) + [1] * (j - weights[i - 1]) + [0] * (n - j)

    return max_profit, best_plan

# 示例
weights = [1, 2, 3]
values = [10, 20, 30]
costs = [1, 2, 3]
source = 0
destination = 3
profit, plan = move_bricks(weights, values, costs, source, destination)
print("最大利润:", profit)
print("搬运方案:", plan)