POJ2782:Bin Packing

Description

A set of n<tex2html_verbatim_mark> 1-dimensional items have to be packed in identical bins. All bins have exactly the same length l<tex2html_verbatim_mark> and each item i<tex2html_verbatim_mark> has length l_il<tex2html_verbatim_mark> . We look for a minimal number of bins q<tex2html_verbatim_mark> such that

• each bin contains at most 2 items,
• each item is packed in one of the q<tex2html_verbatim_mark> bins,
• the sum of the lengths of the items packed in a bin does not exceed l<tex2html_verbatim_mark> .

You are requested, given the integer values n<tex2html_verbatim_mark> , l<tex2html_verbatim_mark> , l₁<tex2html_verbatim_mark> , …, l_n<tex2html_verbatim_mark> , to compute the optimal number of bins q<tex2html_verbatim_mark> .