Near-Equal Container Packing — Problem Statement & Solution Guide
Problem Description
Given a list of cargo crates with their respective weights and a target number of cargo bays, organize the crates into the bays such that the total weight in each bay is as close to equal as possible.
Examples
Input
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 3
Output
[[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]
Explanation: Step-by-step: with input [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] and 3 bays, we first sort the crates by weight. Then, we distribute the crates into the bays as evenly as possible, starting with the heaviest crates. In this case, we get [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]].
Input
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1] 3
Output
[[1, 1, 1, 1, 1], [1, 1, 1], [1, 1, 1]]
Explanation: Step-by-step: with input [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] and 3 bays, we first sort the crates by weight. Then, we distribute the crates into the bays as evenly as possible, starting with the heaviest crates. In this case, we get [[1, 1, 1, 1, 1], [1, 1, 1], [1, 1, 1]].
Constraints
- 1 <= k <= 10
- 1 <= crates.length <= 16
- 1 <= crates[i] <= 100
Optimal Approach & Strategy
The optimal approach involves using a recursive backtracking algorithm with a threshold for the maximum allowed difference in weight between the bays. The algorithm starts by sorting the crates in descending order of their weights and then tries placing each crate in each bay. If a configuration does not lead to a balanced distribution, the algorithm backtracks and tries a different configuration.
Brute Force Approach
A naive approach would involve generating all possible permutations of crates and then checking each permutation to see if it satisfies the condition. However, this approach would have an exponential time complexity. A slightly more efficient brute-force approach would use a recursive function to try placing each crate in each bay, without using any optimization techniques.
Verified Code Solutions
function nearEqualContainerPacking(crates, bays) {
const n = crates.length;
const k = Math.ceil(n / bays);
const result = Array(bays).fill(0).map(() => []);
function backtrack(i, j) {
if (i === n) {
return true;
}
let minDiff = Infinity;
let minIndex = -1;
for (let x = 0; x <= k && i + x <= n; x++) {
const sum = crates.slice(i, i + x).reduce((a, b) => a + b, 0);
const diff = Math.abs(sum - k * (j + 1));
if (diff < minDiff) {
minDiff = diff;
minIndex = i;
}
}
if (minIndex === -1) {
return false;
}
result[j].push(...crates.slice(minIndex, minIndex + k));
if (backtrack(minIndex + k, j + 1)) {
return true;
}
result[j].splice(result[j].length - k, k);
return false;
}
for (let i = 0; i < bays; i++) {
if (!backtrack(0, i)) {
return [];
}
}
return result;
}class Solution {
public int[][] nearEqualContainerPacking(int[] crates, int bays) {
Arrays.sort(crates);
reverse(crates);
int[][] baysList = new int[bays][];
int[] baysWeight = new int[bays];
for (int i = 0; i < bays; i++) {
baysList[i] = new int[crates.length];
}
backtrack(crates, baysList, baysWeight, 0);
return baysList;
}
private void backtrack(int[] crates, int[][] baysList, int[] baysWeight, int index) {
if (index == crates.length) {
return;
}
for (int i = 0; i < baysList.length; i++) {
if (baysWeight[i] + crates[index] <= Arrays.stream(crates).sum() / baysList.length + crates[index]) {
baysList[i][index] = crates[index];
baysWeight[i] += crates[index];
backtrack(crates, baysList, baysWeight, index + 1);
baysList[i][index] = 0;
baysWeight[i] -= crates[index];
}
}
}
private void reverse(int[] array) {
int left = 0;
int right = array.length - 1;
while (left < right) {
int temp = array[left];
array[left] = array[right];
array[right] = temp;
left++;
right--;
}
}
}def near_equal_container_packing(crates, bays):
crates.sort(reverse=True)
bays_list = [[] for _ in range(bays)]
bays_weight = [0] * bays
def backtrack(index):
if index == len(crates):
return True
for i in range(bays):
if bays_weight[i] + crates[index] <= sum(crates) / bays + crates[index]:
bays_list[i].append(crates[index])
bays_weight[i] += crates[index]
if backtrack(index + 1):
return True
bays_list[i].pop()
bays_weight[i] -= crates[index]
return False
backtrack(0)
return bays_listfunction nearEqualContainerPacking(crates, bays) {
const n = crates.length;
const k = Math.ceil(n / bays);
const result = Array(bays).fill(0).map(() => []);
function backtrack(i, j) {
if (i === n) {
return true;
}
let minDiff = Infinity;
let minIndex = -1;
for (let x = 0; x <= k && i + x <= n; x++) {
const sum = crates.slice(i, i + x).reduce((a, b) => a + b, 0);
const diff = Math.abs(sum - k * (j + 1));
if (diff < minDiff) {
minDiff = diff;
minIndex = i;
}
}
if (minIndex === -1) {
return false;
}
result[j].push(...crates.slice(minIndex, minIndex + k));
if (backtrack(minIndex + k, j + 1)) {
return true;
}
result[j].splice(result[j].length - k, k);
return false;
}
for (let i = 0; i < bays; i++) {
if (!backtrack(0, i)) {
return [];
}
}
return result;
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.