Q: Given a building with $n$ floors, each floor $i$ has $c_i$ boxes in it. You need to find a way to store all the boxes in at most $m$ floors. Moving boxes from one floor to another is allowed only from a higher floor to a lower floor, and when boxes are moved from one floor to another, all of the boxes in the floor are moved.
Input:
- $1,2,\dots,n$ represting the floors, s.t. floor $i$ contains $c_i$ boxes in it. The first floor is the lowest and the $n$-th floor is the highest.
- $m\in\lbrace1,2,\dots,n\rbrace$ representing the maximal number of floors allowed for storage of the boxes.
Legal Solution:
$l_1,l_2,\dots,l_m$ representig the floors used for storage.
A partition $F_1,F_2,\dots,F_m$ of the the $n$ floors s.t. for all $1\le j \le m$ and for all $i\in F_j:$ $i\ge l_j$ (that means the boxes are moved only from higher floors to lower floors).
Weight of a legal solution:
- The cost for moving boxes from floor $i$ to floor $l$ is $c_i\cdot(i-l)$. The weight of a solution $l_1,\dots,l_m,F_1,\dots,F_m$ is $\sum\limits_{j=1}^m\sum\limits_{i \in F_i}c_i\cdot(i-l_j)$
Requirement: find a legal solution with minimal weight.
Now, further on there's a requirement to define $n\cdot m$ typical sub problems at most, and to find a recursive formula for the the calcuation of the weight of an optimal solution. Also there's a requirement to find an iterative algorithm, based on the recursive formula, that finds the solution. That's is where I fail, because all my attempts so far didn't led me to a recursive formula that I can lead me to an iterative solution.
My best attempt so far was to define the recursive formula like so: $$OPT(i,j,c_i)=\begin{cases} 0 &\text{ if } i=j\\ \sum\limits_{k=1}^i c_k\cdot(k-1) &\text{ if } i>j=1\\min\lbrace c_j+OPT(i-1,j,c_i+c_{i-1}), OPT(i-1,j-1,c_{i-1}) &\text{ if }i>j>1\end{cases}$$ In this formula $i$ represents the first $i$ floors, $j$ represents the number of allowed floors for storage and $c_j$ represents the number of boxes in the $i$-th floor. I'm not sure that I define only $n\cdot m$ sub problems, and I can't develop an iterative algorithm based on this formula.
Any help would be appreciated, Thanks