I need to make program that solves bin packing problem, but I already made first fit and greedy algorithms, but my lecturer says in some cases it won't find the minimal solution to the problem. So i decided to try bruteforce, but I have no clue how it should check all possible solutions. So yea.. can someone explain to me or give pseudo-code or something. I would appreciate a lot.
Note that bin-packing is an NP-hard problem, basically meaning it will take excessively long to run brute force on it, even for relatively small input, so brute force for NP-hard problems is almost never a good idea. The link above shows some alternatives (or approximations). But I'll continue...
Recursion makes brute force easy. Once you understand a basic recursive algorithm, continue reading...
Basic idea: (for 3 items, 2 bins, assuming everything fits, if it doesn't just skip that branch)
Put the first item in the first bin.
Put the second item in the first bin.
Put the third item in the first bin.
Woo-hoo! We have a solution!
Remove the third item from the first bin and put it into the second bin.
Woo-hoo! We have a solution!
Remove the third item from the second bin.
Remove the second item from the first bin and put it into the second bin.
Put the third item in the first bin.
Woo-hoo! We have a solution!
Remove the third item from the first bin and put it into the second bin.
Woo-hoo! We have a solution!
Remove the third item from the second bin.
Remove the second item from the second bin.
Remove the first item from the first bin and put it into the second bin.
Put the second item in the first bin.
Put the third item in the first bin.
Woo-hoo! We have a solution!
Remove the third item from the first bin and put it into the second bin.
Woo-hoo! We have a solution!
Remove the third item from the second bin.
Remove the second item from the first bin and put it into the second bin.
Put the third item in the first bin.
Woo-hoo! We have a solution!
Remove the third item from the first bin and put it into the second bin.
Woo-hoo! We have a solution!
Remove the third item from the second bin.
Remove the second item from the second bin.
Remove the first item from the second bin.
(See how many steps there is already? And this is just for 3 items and 2 bins)
Pseudo-code:
recurse(int itemID)
if pastLastItem(itemID)
if betterThanBestSolution
bestSolution = currentAssignment
return
for each bin i:
putIntoBin(itemID, i)
recurse(itemID+1)
removeFromBin(itemID, i)