chap limits to computation bin packinginputnumbers xn between and and an unlimited supply of bins of size (no bin can hold numbers whose sum exceeds outputan assignment of numbers to bins that requires the fewest possible bins bin packing in its decision form ( asking if the items can be packed in less than binsis known to be -complete one simple heuristic for solving this problem is to use "first fitapproach we put the first number in the first bin we then put the second number in the first bin if it fitsotherwise we put it in the second bin for each subsequent numberwe simply go through the bins in the order we generated them and place the number in the first bin that fits the number of bins used is no more than twice the sum of the numbersbecause every bin (except perhaps onemust be at least half full howeverthis "first fitheuristic can give us result that is much worse than optimal consider the following collection of numbers of /  of / and of / where is smallpositive number properly organizedthis requires bins but if done wronglywe might end up putting the numbers into bins better heuristic is to use decreasing first fit this is the same as first fitexcept that we keep the bins sorted from most full to least full then when deciding where to put the next itemwe place it in the fullest bin that can hold it this is similar to the "best fitheuristic for memory management discussed in section the significant thing about this heuristic is not just that it tends to give better performance than simple first fit this decreasing first fit heuristic can be proven to require no more than / the optimal number of bins thuswe have guarantee on how much inefficiency can result when using the heuristic the theory of -completeness gives technique for separating tractable from (probablyintractable problems recalling the algorithm for generating algorithms in section we can refine it for problems that we suspect are -complete when faced with new problemwe might alternate between checking if it is tractable (that iswe try to find polynomial-time solutionand checking if it is intractable (we try to prove the problem is -completewhile proving that some problem is -complete does not actually make our upper bound for our algorithm match the lower bound for the problem with certaintyit is nearly as good once we realize that problem is -completethen we know that our next step must either be to redefine the problem to make it easieror else use one of the "copingstrategies discussed in this section