Organizing shipping containers with recursive dynamic programming

Question

I'm trying to solve the following problem using Recursive Dynamic Programming:

Given a shipyard of width W, M cranes to haul containers onto the yard and N shipping containers of varying sizes (), find the minimal cost to organize the N containers with M cranes in rows on the yard.


Some additional constraints:

Leftover space at the end of any row (except the last) incurs an additional cost.
Each crane has different operational costs to move containers onto a row on the yard.
A row is operated by a single crane only.
Cranes can operate on multiple rows (a crane can be assigned to 0 rows, or multiple).
Cranes are assigned to rows in increasing order (as well as containers), so if crane c is assigned to a row, cranes with index  cannot be used anymore.


I have calculated two helper arrays with the following costs:

Array row_costs[N][N]: the additional cost for putting containers i through j in a single (non-final) row, with __MAX_COST__ for combinations of containers that exceed the width of the shipyard.
Array crane_costs[M][N][N]: the cost for using crane c to move containers i through j onto rows.

I have the following code, which works fine if not both crane_c and container_j are greater than 1 (>0). My indexing of cranes and containers are from 0 to M-1, and N-1, respectively.
This is my code:
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;
  }
}

Maybe I'm going about it totally wrong, as I've been looking at a dozen other DP problems, and the structure of my clauses feel different. I'm struggling with the adding of the additional row_costs[][] in prior (non-final) rows with this final clause.
Update
I have updated the clause crane_c == 1 && container_j > 0. This now feels more in line with how I've seen recursion is applied in other DP problems and how the state-space tree is traversed. I feel like I'm very near in finding the solution for the last clause.

Organizing shipping containers with recursive dynamic programming

0 Answers