# Bin packing problem and optimality proof

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?

• Who said it's Optimal?and where is the bin size in your example?. The original Bin Packing problem is known to be NP Complete, any polynomial time algorithm will give u an approximate solution (hopefully near optimal)
– ShAr
Sep 29, 2021 at 7:44
• What are we trying to achieve ? Are we trying to minimize the number of bins needed ? Nov 25, 2021 at 23:36

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).
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).