Algorithm for minimum sacks required to accommodate all the given elements

Revision en2, by ujjaldas223, 2019-10-27 09:40:49

Problem: Given an array which contains weights of given elements A = [W1, W2, .., Wn]. Unlimited sacks are available which has the limit to bear some weights say X.

It is always guaranteed that X >= Wi, 1 <= i <= n.

What is the minimum number of sacks need to fill all the elements in the array? Display the content of each sacks.

Test case 1:

X = 10, A = [5, 4, 2, 6, 7, 8, 3, 1]

Ans: Content of sacks: [8, 2], [7, 3], [6, 4], [5, 1]

Test case 2:

X = 15, A = [5, 1, 10, 9]

Ans: Content of sacks: [1, 5, 9], [10]

I have tried greedy method, which will pick elements from first to last and fill the sacks. But this solution is not optimal. Can you suggest any optimal solutions for the above problem?

Tags #algorithms, #c++

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English ujjaldas223 2019-10-27 09:40:49 20
en1 English ujjaldas223 2019-10-27 09:39:52 851 Initial revision (published)