递归动态规划求解船坞集装箱排布最小成本实现问题

问题描述 #

我正在尝试使用递归动态规划求解如下问题：
给定宽度为W的船坞、M台用于将集装箱吊运至堆场的起重机，以及N个尺寸各异（所有集装箱尺寸均<W）的海运集装箱，求解使用M台起重机将N个集装箱按行排布在堆场上的最小成本。
附加约束如下：

• 除最后一行外，任意行末尾的剩余空间都会产生额外成本
• 每台起重机将集装箱吊运至堆场某一行的运营成本各不相同
• 单一行仅可由一台起重机操作
• 起重机可操作多行（单台起重机可分配0行或多行任务）
• 起重机与集装箱均按递增顺序分配：若某行分配了索引为c的起重机，则索引小于c的起重机不可再被使用

预计算辅助数组 #

我已经预先计算得到两个成本辅助数组：

• row_costs[N][N]：将索引i到j的集装箱放置在同一非末尾行产生的额外成本，若该组集装箱总宽度超出船坞宽度则取值为__MAX_COST__
• crane_costs[M][N][N]：使用索引为c的起重机将索引i到j的集装箱吊运至对应行产生的成本

当前实现进展与问题 #

现有代码仅在crane_c与container_j不同时大于0时可正常运行，其中起重机索引范围为0到M-1，集装箱索引范围为0到N-1。
现有代码如下：

double TotalCosts(int crane_c, int container_j)
{
  double minimal_costs, temp;
  int i, k;

  if (crane_c < 0 || container_j < 0)
    return __MAX_COST__;

  if (crane_c == 0 && container_j == 0)
    return crane_costs[crane_c][container_j][container_j];

  if (crane_c > 0 && container_j == 0){
    return min(crane_costs[crane_c][container_j][container_j],
               TotalCosts(crane_c-1, container_j));
  }

  if (crane_c == 0 && container_j > 0){
    if (row_costs[0][container_j] == __MAX_COSTS__)
      minimal_costs = __MAX_COSTS;
    else
      minimal_costs = crane_costs[crane_c][0][container_j];

    for (i = 0; i < container_j; ++i){
      temp = crane_costs[crane_c][i+1][container_j]
           + row_costs[i][container_j-1]
           + TotalCosts(crane_c, i);
      minimal_costs = min(minimal_costs, temp);
    }
    for (i = container_j-1; i > 0 && row_costs[i][container_j] != __MAX_COSTS__; --i){
      temp = crane_costs[crane_c][i][container_j]
           + row_costs[i-1][i-1]
           + TotalCosts(crane_c, i-1);
      minimal_costs = min(minimal_costs, temp);
    }
    return minimal_costs;
  }

  if (crane_c > 0 && container_j > 0){
    if (row_costs[0][container_j] == __MAX_COSTS__)
      minimal_costs = __MAX_COSTS__;
    else
      minimal_costs = crane_costs[crane_c][0][container_j];

    for (k = crane_c; k >= 0; --k){
      for (i = 1; i <= container_j; ++i){
        
        //...

        minimal_costs = min(minimal_costs, temp);
      }
    }
    return minimal_costs;
  }
}

我怀疑当前实现思路存在偏差，参考大量其他动态规划问题实现后，发现现有分支结构和常规DP实现差异较大，目前卡在最后一个分支（crane_c>0且container_j>0）的逻辑补全上，无法正确计算前置非末尾行对应的row_costs[][]额外成本。

更新：我已更新crane_c == 1 && container_j > 0对应的分支逻辑，目前该部分逻辑更贴合其他DP问题中的递归实现范式与状态空间树遍历逻辑，距离补全最后一个分支的逻辑已非常接近，求助正确的实现方案。

内容的提问来源于stack exchange，提问作者mikoflip