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

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!

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.
• Since there are only finitely many options for $i(O)$, I don’t see any problems. – Yuval Filmus May 1 '20 at 23:01