Proof of a greedy algorithm used for a variation of bin-packing problem

Question

We are given an array of weights $W$ (all weights are positive integers), and we need to put the weights inside bins. Each bin can hold a maximum of Max_val, and each weight is at most Max_val. The variation is that the ordering of weights should not be changed, that is, $W_i$ should be inside a bin before $W_j$ is inserted, for all $i < j$.

For this problem statement, intuitively we can see that a greedy approach of filling a bin till its maximum value is reached and creating a new bin for further weights will produce the minimum number of bins. I am unable to come up with a formal proof that the greedy solution is optimal. Any hints or guidelines would be great!

Answer 1

Let $G$ be the solution produced by the greedy algorithm. For each other solution $S$, let $i(S)$ be the index of the first weight at which $S$ diverges from $G$. Let $O$ be an optimal solution maximizing $i(O)$. Thus $G$ places $i(O)$ in bin $j$ (for some $j$), and $O$ places $i(O)$ in bin $j+1$. If we move $i(O)$ to bin $j$ (which is possible since $O$ is ordered), we obtain a solution $O'$ using at most as many bins as $O$, and satisfying $i(O') > i(O)$. This contradicts the choice of $O$.

If we try to run this argument on the unrestricted bin packing algorithm, we will have trouble when moving $i(O)$ to bin $j$, since that bin might be occupied with other elements, not leaving enough room for $i(O)$. In the variant you consider, this cannot happen.