So I'm trying to learn bin-packing for a tool that I need create. So I used the following code from Bin Packing Problem (Minimize number of used Bins)
Fiddle: Wood Pieces Fiddle
int[] weight = { 345,345,175,175,175,175,470,470,470,470,345,345,175,175,200,200,200,200,300,300,400,400,350 };
int c = 3000;
int n = weight.Length;
Console.Write("Total: " + weight.Sum() + "mm in " + GFG.bestFit(weight, n, c) + " pieces max");
and the working routine:
public static int bestFit(int[] weight, int n, int c)
{
// Initialize result (Count of bins)
int res = 0;
// Create an array to store
// remaining space in bins
// there can be at most n bins
int[] bin_rem = new int[n];
// Place items one by one
for (int i = 0; i < n; i++) {
// Find the best bin that
// can accommodate
// weight[i]
int j;
// Initialize minimum space
// left and index
// of best bin
int min = c + 1, bi = 0;
for (j = 0; j < res; j++) {
if (bin_rem[j] >= weight[i]
&& bin_rem[j] - weight[i] < min) {
bi = j;
min = bin_rem[j] - weight[i];
}
}
// If no bin could accommodate weight[i],
// create a new bin
if (min == c + 1) {
bin_rem[res] = c - weight[i];
res++;
}
// Assign the item to best bin
else
bin_rem[bi] -= weight[i];
}
return res;
}
So I've two questions, but mainly only one:
Mainly question: How can I get the result of the total bins and the pieces of each bin? I tried to modify the routine to a List<> but I fail misserabily. I don't need the answer AS-IS, with a idea or approach will fine because I'm not looking for someone to work for me, only a help to understand where is the catch on this. Any help will be preciated, even a comment.
Optional question: I don't think is the best method (If I understand well) because doesn't try all combinations and possibilities. There is any guide to improve this code?
I'd suggest to keep a single data structure to keep all your result data, so that you don't have to keep two datastructures aligned.
Furthermore, I'd suggest to use a datastructure like List or similar, because it's more flexible than arrays. Ie you don't know, how many bins there will be and how many items there will be in a bin. So allocating non-resizable arrays may not be the best approach, because you either have to make them big enough to contain all elements (and waste a lot of memory) or you always have to check their size and reallocate if necessary.
Futhermore, as explained in the comments, I'd suggest to sort the items descending before distributing them into the bins, because this way, the heavy items that won't fit into one bin togehter will be distributed first, and then the light items can be used to fill up the remainig gaps. If you distribute the light items first, they will be tightly packed into the first few bins. And then each of the heavy items will need a bin for itself, leaving a lot of unused capacity.
See the following code for a simple implementation of that approach
//the default capacity of an empty bin
private static in CAPACITY = 3000;
//this is the structure that will represent a single bin, exposing the
//remaining capacity and the items currently contained
class Bin {
public int capacityLeft {get; set;}
public List<int> items { get; set;}
}
//alternatively you can also pass an int[] here
//doesn't make any difference
static List<Bin> distributeItems(List<int> items) {
//create new result list of bins
var result = new List<Bin>();
//sort the items according to comments above
//try also just with OrderBy(x => x) to sort ascending and see
//the effect on the result
var sortedItems = items.OrderByDescending(x => x);
foreach (var x in sortedItems) {
if (x > CAPACITY) {
//skip items that are too heavy, or throw an error if you want
//throw new Error($"item {x} is too heavy");
continue;
}
//the smallest remaining capacity so far
var min = CAPACITY + 1;
//the index of the bin where to put the current item to
var index = result.Count;
//check through all existing bins
//for the first item, this list will be empty, so the loop's body
//won't be executed at all
for (int i = 0; i < result.Count; i++) {
//does the current bin have enough capacity left
//and is that remaining capacity minimal?
if (result[i].capacityLeft >= x && result[i].capacityLeft < min) {
//define the current bin to be the target for the item
min = result[i].capacityLeft;
index = i;
}
}
//if no fitting bin was found, index will still be result.Count
//ie pointing "after" the last element in the result list.
//this also works for the empty list, as result.Count == index == 0
//if thats the case, append a new empty bin to the result
if (index == result.Count) {
result.Add(new Bin{capacityLeft = CAPACITY, items = new List<int>()});
}
//put the current item in the respective bin (either the one found
//in the loop, or the one newly added to the list)
result[index].capacityLeft -= x;
result[index].items.Add(x);
}
return result;
}
See also this fiddle for a complete working example ...