Bin packing problem and optimality proof

Question

Let $W$ be an array of weights. Store all the weights of $W$ in bins such that in each bin a heavier weight always go before a lighter weight (if $w_i\in W$ is stored before $w_j\in W$ then necessarily $w_i > w_j$), and the original order of the weights in $W$ is preserved ($w_i \in W$ cannot be stored before $w_j \in W$ if $i>j$). There is no restriction on the maximum value of the weights or capacity of the bins.

I have come up with the following greedy algorithm: for every weight $w_i$ in $W$, store it in the first bin available that is compatible with the restrictions given. For example, for the entry $[47, 27, 33, 5, 13]$, the algorithm's output would be $[47, 27, 5]$ and $[33, 13]$. How can I prove that this algorithm is optimal?

Answer 1

Your solution is not optimal. Take for example, the following list of weights: $[1,4,3,2]$. In this example, your algorithm will place only $1$ in the bins, whilst a different solution could place $4,3$ and $2$ instead (which is obviously a better solution).

However, you can create a dynamic programming solution for this problem:

Consider the graph $G$, with vertices corresponding to the weights in $W$, and edges $(w_i,w_j)$ if $j>i$ ($w_j$ is after $w_i$) and $w_i>w_j$ ($w_j$ must be lighter than $w_i$ for us to place it after $w_i$). We will also place an edge-weight on every such edge equal to the weight in $w_j$ (which intuitively means that if we traverse this edge, we add $w_j$ to the bins).

This graph is a DAG, and the optimal solution for your problem can be proven to be the longest (in terms of edge-weights) path in this graph. Since this is a DAG, you can construct a dynamic programming solution for it.