0
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ 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) $\endgroup$
    – ShAr
    Sep 29, 2021 at 7:44
  • $\begingroup$ What are we trying to achieve ? Are we trying to minimize the number of bins needed ? $\endgroup$ Nov 25, 2021 at 23:36

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.