动态规划解决双容量队列物品分配最低成本问题

问题描述

假设我们有一个包含n个物品的队列，需要将这些物品依次分配到两个容量相同的集合中。每个集合都有一个最大容量限制，物品分配时不能超出此限制。分配规则如下：

1. 每个物品都必须被分配到一个集合中。
2. 除非支付一定的成本，否则当前物品必须进入其前一个物品所进入的集合。
3. 我们希望找到一种分配方案，使得所有物品都被分配完毕，且总成本最低。

成本由一个数组 cost = [a1, a2, ..., an] 表示，其中 ai 是将第 i 个物品分配到与第 i-1 个物品不同集合时需要支付的成本。

暴力解法及其局限性

原始问题中提供了一个递归的暴力解法思路：

def solve_bruteforce(i, h1_used, current_set_id, n, C, costs):
    # i: 当前考虑的物品索引
    # h1_used: 集合1已使用的容量
    # current_set_id: 前一个物品进入的集合ID (1或2)
    # n: 总物品数
    # C: 单个集合的最大容量
    # costs: 成本数组

    if i > n:
        return 0 # 所有物品已分配

    h2_used = (i - 1) - h1_used # 集合2已使用的容量

    # 如果集合1已满
    if h1_used == C:
        if current_set_id == 1: # 如果前一个物品在集合1，现在集合1满了，必须切换到集合2
            return costs[i - 1] + solve_bruteforce(i + 1, h1_used, 2, n, C, costs)
        else: # 前一个物品在集合2，且集合1满了，继续在集合2
            return solve_bruteforce(i + 1, h1_used, 2, n, C, costs)
    # 如果集合2已满
    elif h2_used == C:
        if current_set_id == 2: # 如果前一个物品在集合2，现在集合2满了，必须切换到集合1
            return costs[i - 1] + solve_bruteforce(i + 1, h1_used + 1, 1, n, C, costs)
        else: # 前一个物品在集合1，且集合2满了，继续在集合1
            return solve_bruteforce(i + 1, h1_used + 1, 1, n, C, costs)
    # 两个集合都未满
    else:
        if current_set_id == 1: # 前一个物品在集合1
            # 选项1: 继续在集合1 (不支付成本)
            cost_continue_1 = solve_bruteforce(i + 1, h1_used + 1, 1, n, C, costs)
            # 选项2: 切换到集合2 (支付成本)
            cost_switch_to_2 = costs[i - 1] + solve_bruteforce(i + 1, h1_used, 2, n, C, costs)
            return min(cost_continue_1, cost_switch_to_2)
        else: # 前一个物品在集合2
            # 选项1: 切换到集合1 (支付成本)
            cost_switch_to_1 = costs[i - 1] + solve_bruteforce(i + 1, h1_used + 1, 1, n, C, costs)
            # 选项2: 继续在集合2 (不支付成本)
            cost_continue_2 = solve_bruteforce(i + 1, h1_used, 2, n, C, costs)
            return min(cost_switch_to_1, cost_continue_2)

这个暴力解法通过递归探索所有可能的分配路径。然而，它存在大量的重叠子问题。例如，在处理第 i 个物品时，无论前一个物品是进入集合1还是集合2，都可能面临相同的剩余物品数量和集合容量状态。这种重复计算导致其时间复杂度呈指数级增长，对于较大的 N 值是不可接受的。

动态规划优化

为了解决暴力解法的效率问题，我们可以采用动态规划（Dynamic Programming, DP）结合记忆化（Memoization）技术。DP的核心思想是存储并重用已计算过的子问题结果，避免重复计算。

状态定义

为了有效地应用DP，我们需要定义一个能够唯一标识子问题的状态。一个合适的DP状态可以表示为 dp(i, cap1_rem, cap2_rem)：

• i: 当前正在考虑的物品索引（从0到N-1）。
• cap1_rem: 集合1剩余的容量。
• cap2_rem: 集合2剩余的容量。

然而，更简洁的状态定义可以利用问题中的对称性，如答案中提示的“cap1 总是上次使用的集合的容量”。这样，我们只需要跟踪当前物品索引和两个集合的剩余容量，其中一个集合被约定为“上次使用的集合”。

我们定义 solve(i, cap_last_used, cap_other) 为：从第 i 个物品开始，当上次使用的集合剩余容量为 cap_last_used，另一个集合剩余容量为 cap_other 时，将剩余物品分配的最低成本。

递推关系

对于 solve(i, cap_last_used, cap_other)，我们有两种决策：

1. 切换到另一个集合（Switch to Other Set）：

   • 如果选择将当前物品 i 放入“另一个集合”，则需要支付 cost[i]。
   • 放置后，“另一个集合”的容量 cap_other 减少1。
   • 原先的“另一个集合”现在变成了“上次使用的集合”，其剩余容量为 cap_other - 1。
   • 原先的“上次使用的集合”现在变成了“另一个集合”，其剩余容量为 cap_last_used。
   • 此操作的成本为：cost[i] + solve(i + 1, cap_other - 1, cap_last_used)。
   • 前提条件：cap_other > 0 (另一个集合必须有容量)。

2. 继续使用上次使用的集合（Continue Last Used Set）：

   

   幻舟AI

   专为短片创作者打造的AI创作平台

   279

   查看详情
   • 如果选择将当前物品 i 放入“上次使用的集合”，则不需要支付额外成本。
   • 放置后，“上次使用的集合”的容量 cap_last_used 减少1。
   • “上次使用的集合”仍然是“上次使用的集合”，其剩余容量为 cap_last_used - 1。
   • “另一个集合”的剩余容量 cap_other 保持不变。
   • 此操作的成本为：solve(i + 1, cap_last_used - 1, cap_other)。
   • 前提条件：cap_last_used > 0 (上次使用的集合必须有容量)。

基本情况（Base Case）： 当 i == n 时，表示所有物品都已分配完毕，此时成本为0。

伪代码实现

结合上述状态定义和递推关系，我们可以得到以下伪代码（类似Python）：

# 使用字典或数组实现记忆化
memo = {}

def cinema(n_items, initial_capacity, costs):
    # 初始调用：从第0个物品开始，两个集合的初始容量都是 initial_capacity
    # 这里的 cap_last_used 和 cap_other 初始时都代表总容量
    # 由于是第一个物品，可以认为它进入哪个集合都不算“切换”，或者约定一个默认的初始状态
    # 答案中的实现巧妙地将两个集合的初始容量都作为参数传入
    # 假设初始时，两个集合都是可用的，且没有“上次使用的集合”的概念，
    # 我们可以将任一集合视为“上次使用的”，并让其容量为 initial_capacity，另一个也为 initial_capacity。
    # 这样可以简化为 solve(0, initial_capacity, initial_capacity, n_items, costs)
    # 答案的 cinema(n,0,B,B,cost) 中，n是总物品数，0是当前物品索引，B是两个集合的初始容量
    return solve(0, initial_capacity, initial_capacity, n_items, costs)

def solve(i, cap_last_used, cap_other, n_items, costs):
    # 记忆化查找
    if (i, cap_last_used, cap_other) in memo:
        return memo[(i, cap_last_used, cap_other)]

    # 基本情况：所有物品都已处理
    if i == n_items:
        return 0

    # 选项1: 切换到另一个集合
    # 确保另一个集合有容量
    cost_to_switch = float('inf') # 初始化为无穷大
    if cap_other > 0:
        # 注意：这里 costs[i] 是将第 i 个物品切换到不同集合的成本
        cost_to_switch = costs[i] + solve(i + 1, cap_other - 1, cap_last_used, n_items, costs)

    # 选项2: 继续使用上次使用的集合
    # 确保上次使用的集合有容量
    cost_to_continue = float('inf') # 初始化为无穷大
    if cap_last_used > 0:
        cost_to_continue = solve(i + 1, cap_last_used - 1, cap_other, n_items, costs)

    # 如果上次使用的集合已满，则必须切换 (即只能选择 cost_to_switch)
    # 否则，取两种选择的最小值
    result = float('inf')
    if cap_last_used == 0:
        result = cost_to_switch
    else:
        result = min(cost_to_switch, cost_to_continue)

    # 存储结果并返回
    memo[(i, cap_last_used, cap_other)] = result
    return result

# 示例调用 (假设 N=5, C=3, costs=[1,2,3,4,5])
# total_cost = cinema(5, 3, [1,2,3,4,5])
# print(total_cost)

注： 答案中提供的伪代码 if cap1==0: return cost_to_switch 是一个巧妙的简化，它将“必须切换”的情况直接处理，避免了 min 函数中无效的选择。这隐含了 cost_to_switch 总是有效的前提（即 cap2 > 0）。在实际实现中，需要确保任何选择都满足容量限制。上述更详细的伪代码考虑了 cap_other > 0 和 cap_last_used > 0 的检查。

复杂度分析

• 时间复杂度：

  • i 的取值范围：从 0 到 N (共 N+1 种)。
  • cap_last_used 的取值范围：从 0 到 C (共 C+1 种，C 为单个集合的最大容量)。
  • cap_other 的取值范围：从 0 到 C (共 C+1 种)。
  • 每个状态的计算是 O(1) (常数时间，因为只是比较和递归调用)。
  • 因此，总的时间复杂度为 O(N * C * C)。
  • 在最坏情况下，C 可以接近 N (例如，如果一个集合可以容纳所有物品，另一个集合容量为0，但通常情况下 C 是 N/2 左右)。如果 C 与 N 同阶，则时间复杂度为 O(N * N * N) = O(N^3)。这符合题目要求的复杂度。

• 空间复杂度：

  • 记忆化表格 memo 存储了所有计算过的状态。
  • 状态的数量与时间复杂度中的状态数相同，所以空间复杂度为 O(N * C^2)，同样是 O(N^3)。

实现细节与注意事项

1. 记忆化实现：

   • 在Python中，最方便的实现方式是使用 functools.lru_cache 装饰器。只需将它添加到 solve 函数上方，它会自动处理记忆化。
   • 手动实现时，可以使用一个字典（如 memo = {}）来存储 (i, cap_last_used, cap_other) 作为键，对应的最低成本作为值。在每次 solve 调用开始时检查 memo，结束时更新 memo。

2. 初始调用：

   • cinema(n_items, initial_capacity, costs) 的 initial_capacity 应该设置为两个集合各自的初始最大容量。
   • solve 函数的初始 cap_last_used 和 cap_other 都应为 initial_capacity。由于是第一个物品，可以认为它进入哪个集合都不算“切换”，或者根据实际业务需求定义第一个物品的成本。本方案中 costs[0] 视为第一个物品的切换成本。

3. 容量约束：

   • 在递归调用之前，务必检查目标集合是否有足够的剩余容量 (cap > 0)。如果容量不足，则该选项不可选。在伪代码中已通过 if cap_other > 0 和 if cap_last_used > 0 进行了体现。

4. 对称性处理：

   • 答案中提到的“cap1 总是上次使用的集合的容量”是一个关键的简化。它避免了在状态中明确区分“集合1”和“集合2”的物理ID，而是动态地将“上次使用的集合”和“另一个集合”作为逻辑概念来处理，大大简化了状态表示和递推逻辑。

以上就是动态规划解决双容量队列物品分配最低成本问题的详细内容，更多请关注php中文网其它相关文章！