I dont think the greedy approach gives the optimal solution here. Take the below case -
Items are - 5, 4X2, 3, 2X2 and bins are of size 10. Greedy approach will make choice in order - bin1 - 5 + 4 bin2 - 4 + 3 + 2 bin3 - 2 Total bins required - 3 While in optimal solution - bin1 - 5 + 3 +2 bi2 - 4 + 4 + 2 Total bins required - 2 Need to used DP approach similar to 0-1 knapsack. Feedback welcome :-), - Ravindra On Sat, Oct 29, 2011 at 7:52 PM, icy` <[email protected]> wrote: > yea, i'd go with greedy also. Fill bin with biggest size s1 as much > as possible (and same for other bins), then try to squeeze in next > biggest size s2, etc. > > On Oct 29, 7:17 am, teja bala <[email protected]> wrote: > > Greedy knapsack algorithm will work fine in this case as in each bin > > > > n1s1+n2s2+..nrsr<=C gives the optimal solution........... > > > > > > > > > > > > > > > > On Sat, Oct 29, 2011 at 4:34 AM, SAMMM <[email protected]> wrote: > > > Suppose u have n1 items of size s1, > > > n2 items of size s2 and n3 items of size s3. You'd like to pack > > > all of these items into bins each of capacity C, such that the > > > total number of bins used is minimized. > > > > > -- > > > You received this message because you are subscribed to the Google > Groups > > > "Algorithm Geeks" group. > > > To post to this group, send email to [email protected]. > > > To unsubscribe from this group, send email to > > > [email protected]. > > > For more options, visit this group at > > >http://groups.google.com/group/algogeeks?hl=en. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
