I think DP approach with bounded knapsack algorithm can be used to ensure tht the first Bin of filled optimally then the second bin to be filled until no elements remains.
On 10/29/11, ravindra patel <[email protected]> wrote: > 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. > > -- Somnath Singh -- 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.
