1
$\begingroup$

Assume a tower with $n$ floors.

Each floor contains $C_i$ boxes such that $C_i>0$ for all $1\le i\le n $

Moving $C_i$ boxes from floor $i$ to floor $j$ where $i>j$ costs $C_i\cdot(i-j)$ and we can only move all the boxes at once, and they all go to the same floor. (The boxes can only be moved downstairs) Given $C_i$ for all $1\le i\le n$ and integer $m$, choose $m$ floors and a partition of the boxes so that all the boxes can be moved to the $m$ chosen floors with minimal move cost.

Input: $C_1,C_2,\dots C_n$ and number of target floors $m\in \mathbb{N}$

An example: $n=4,C_1=1,C_2=2,C_3=2,C_4=3,m=2 $

So we need to choose 2 floors in which all the boxes will be after moving, we must choose the lowest floor as we cant take those boxes upwards, and another floor, the best floor is the 3rd floor here. (If we choose top floor we use $2$ moves to move from $F_2\mapsto F_1$ and $2\cdot 2$ moves to move from $F_3 \mapsto F_1 $) enter image description here

How to find an algorithm to calculate the minimal cost of moving all the boxes to some $m$ floors? I tried doing a brute-force method of just choosing $\binom{n}{m}$ floors and calculating all the costs from each floor to the nearest target floor, but I need to do a dynamic programming approach here, yet can't find the formula or the data structure to use former results.

I also tried a greedy approach but it didn't seem to even work for simple cases.

$\endgroup$
3
  • 1
    $\begingroup$ Have you tried following the systematic approach to dynamic programming problems that we outline at cs.stackexchange.com/tags/dynamic-programming/info? If not, I would recommend that as the first step. What is your question? The only question I can see is "Any suggestion as of how to to this?", but I can't understand what that is asking. A word seem missing, and I'm not clear on what "this" is. I'm not sure what you mean by "move all the boxes at once". Can you credit the original source where you encountered this task? What is the difference between $M$ vs $m$? $\endgroup$
    – D.W.
    Nov 30, 2022 at 23:02
  • $\begingroup$ I don't understand what the inputs to the problem are. Is a set of target floors provided? How does $M$ influence which solutions are acceptable? What do you mean by "find a partition of the boxes"? I don't understand how the partition relates to the set of moves the problem statement refers to. $\endgroup$
    – D.W.
    Nov 30, 2022 at 23:05
  • $\begingroup$ M is part of the input,an integer that says how many floors will contain boxes after all the moves. The optimal solution consists of a set of floors $F_1,F_2,F_M$ that the boxes will be, where optimality means least cost(move as little boxes according to the formula $C_i(i-j)$ where $i $ is the starting floor of the boxes and $j$ is the target floor(part of the M floors) I have tried writing a few examples with just brute force calculations for $m=1$ and $m=2$ but couldn't find the rule to build a recursive solution that leads to $OPT(i,j)=f(former OPTS) $ as needed. $\endgroup$ Nov 30, 2022 at 23:43

1 Answer 1

4
$\begingroup$

The difficulty of solving many hard problems using dynamic programming is to create/imagine/formulate/decide/select the subproblems with the right number of dimensions/parameters.

While the subproblems cannot be too many to include all dimensions of the problem that we are basically applying brute force, they cannot be too few for us to establish the recurrence relations. The principle of more-subproblems suggests the more subproblems, the easier to solve the bigger subproblems. We want to describe/select subproblems with enough appropriate conditions/precision so that the solutions to smaller ones can be useful and extended to solutions to larger subproblems. $\newcommand{\F}{\mathscr F}$

Subproblems and recurrence relation

The subproblems for this problem are, I would propose, what are the minimum moves to move all boxes to $f$ floors that include floor $h$ as the highest floor among them and floor $1$, where $1\le f\le m$ and $f\le h\le n$. The specification of the highest floor enables us to take advantage of the optimal substructure hereof to establish some recurrence relation; in contrast, if the subproblems are the minimum moves to $f$ floors simply, we cannot establish a recurrence relation.

Denote the number of moves in those minimum moves by $\ell[f][h]$.

The recurrence relation is, for $f\ge3$, $$\ell[f][h]=\min_{f-1\le h^-\le h-1}(\ell[f-1][h^-]-s[h]\times(h-h^-)),\tag{***}\label{***}$$ where $s[h]$ is the total number of boxes at floor $h$ and above. The base case are $\ell[1][1]=\sum_{i=1}^nC_i(i-1)$ and $\ell[2][h]=\ell[1][1]-s[h](h-1)$. The sought answer is the minimum among all $\ell[m][h]$, where $m\le h\le n$.

Call a group of floors that includes floor $1$ a selection. Abusing $\ell$, for a selection $\F$, let $\ell(\F)$ be the number of total moves to move each given box to the nearest floor in $\F$, i.e., the highest floor not higher than the given box. Call a selection an optimal selection if it has the least $\ell(\cdot)$ among all selections with the same number of floors and the same highest floor as itself.

Let $\F$ be an optimal selection. Let $\F^-$ be $\F$ without its highest floor. Then $\F^-$ must be an optimal selection, too. Had it not been, we could have replaced $\F^-$ in $\F$ with an optimal selection with the same number of floors and the same highest floor as $\F^-$ while keeping the highest floor of $\F$ to obtain a selection that leads to less moves, which contradicts with $\F$ being an optimal selection.

Note that $\ell(\F)=\ell(\F^-)-s[h]*(h-h^-)$, where floor $h$ and $h^-$ are the highest floor and the second highest floor in $\F$ respectively, since all boxes in $\F$ will be moved to the same floor as if in $\F^-$, except the boxes that are in floor $h$ and above, each of which will be moved to floor $h$ instead of floor $h^-$.

Suppose $\F$ has $f$ floors. Then $\F^-$ has $f-1$ floors. Letting $h^-$ range through all possible values, we obtain the recurrence relation $\eqref{***}$.

The explanation above focuses on the minimum moves. Adding bookkeeping to track the floor selected along the computation, we can obtain the selection that attain the minimum moves.

Complexity

It takes $O(n)$ to compute all $n$ numbers $s[h]$.

The number of entries $\ell[f][h]$ is at most $mn$. Thanks to $\eqref{***}$ and memoization, it takes $O(h-f+1)=O(n)$ time to compute each entry $\ell[f][h]$.

It takes $O(n)$ to compute the sought answer from $\ell[m][h]$'s.

The total time-complexity is $O(n) + O(mn\,n) + O(n) = O(mn^2)$.

The space-complexity is $O(mn)$.

$\endgroup$
1
  • $\begingroup$ Instead of cost, this answer considers the number of moves. Each move moves one box one floor below. Since "moving $C_i$ boxes from floor $i$ to floor $j$ where $i>j$ costs $C_i\cdot(i-j)$", the number of moves is the same as the cost. $\endgroup$
    – John L.
    Dec 1, 2022 at 15:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.