[Java] Bin Packing problem
Problem at hand is essentially the well known Bin Packing Problem which is NP-hard.\ntasks[i] \u21D2 size of an item or items[i]\nsessionTime \u21D2 capacity of
Problem at hand is essentially the well known [Bin Packing Problem](https://en.wikipedia.org/wiki/Bin_packing_problem) which is NP-hard.\ntasks[i] \u21D2 size of an item or items[i]\nsessionTime \u21D2 capacity of each bin\nGoal: minimize the number of sessions \u21D2 minimize the number of bins\n\nThere are couple of approximation algorithms for Bin packing like First-Fit, Best-Fit and Next-Fit which work well in practice but an efficient algorithm for optimal result is quite hard. This is where small input limits help us, we can just do a brute force i.e. enumerate all possibilities.\n\n**Basic approach**\n1. Maintain an array of ```bins``` of size ```n``` (because we don\'t need more than ```n``` bins for ```n``` items) and a counter ```used``` to keep track of bins used so far. ```bins[i]``` represents size occupied by all the items in ```i```\'th bin. ```bins[i]``` should never exceed ```capacity```.\n2. Do a backtracking and try to assign current item ```items[index]``` to all the available ```bins``` as long as they can accomodate it. Also explore the possibility of creating a new bin (```used++```) for this current item.\n3. Once all the items have been assigned to some bins, take the minimum of number of bins used (use a global variable for result). That is our answer.\n\n**Optimization**\n1. Use [Branch and bound](https://en.wikipedia.org/wiki/Branch_and_bound) technique. If we have already figured out through one of the terminal paths (i.e. valid assignments of all items) that **b** bins are sufficient, then we need not explore paths that we already know will lead to **>= b** bins as the result.\n2. No need to try assigning an item to multiple bins with the same size. 2 bins ```bins[i]``` and ```bins[j]``` of equal size are both identical as far as the backtracking for rest of the items goes, so we just try assign the current item to only one of them and explore that path only. We can use a Set for this in the code.\n3. Sort the items and try to assign items in larger to smaller order. This would help us to arrive at a reasonable estimate early.\n*Note:* I hate the fact that Java doesn\'t have ```Arrays.sort(int[], Comparator<Integer>)```. That\'s the only reason I had to iterate ```index``` in reverse order otherwise I had no intention to confuse readers. :)\n\n```\n// 2 ms. 100%\nclass Solution {\n    private int best;\n    private void assign(int[] bins, int used, int[] items, int index, int capacity) {\n        if(used >= best) return;\n        if(index < 0) {\n            best = used;\n            return;\n        }\n\t\tSet<Integer> set = new HashSet<>();\n        for(int i = 0; i < used; i++) {\n\t\t\tif(!set.add(bins[i]) continue;\n            if(bins[i] + items[index] <= capacity) {\n                bins[i] += items[index];\n                assign(bins, used, items, index - 1, capacity);\n                bins[i] -= items[index];\n            }\n        }\n        bins[used] = items[index];\n        assign(bins, used + 1, items, index - 1, capacity);\n        bins[used] = 0;\n    }\n    public int minSessions(int[] tasks, int sessionTime) {\n        Arrays.sort(tasks);\n        best = tasks.length;\n        assign(new int[tasks.length], 0, tasks, tasks.length - 1, sessionTime);\n        return best;\n    }\n}\n```\n\nTime complexity: O(n log n + n B<sub>n</sub>) = O(n B<sub>n</sub>) where B<sub>n</sub> represents n\'th [Bell number](https://en.wikipedia.org/wiki/Bell_number). B<sub>n</sub> counts the number of different ways to partition a set of n elements.\nSpace complexity: O(n<sup>2</sup>) [O(n) if we don\'t use Set optimization]
[]