mediumBacktrackingPattern: Backtracking
Distribute Items into Containers Solution
Problem Statement
You are given two lists of integers: `itemWeights` representing the weights of items, and `containerCapacities` representing the capacities of containers. Your task is to assign items to containers such that the total weight of items in each container does not exceed its capacity. The goal is to find an assignment that maximizes the number of items distributed. If multiple assignments distribute the maximum number of items, any one of them is acceptable.
Examples
Example 1:
Input:{"itemWeights":[1,2,3,4,5],"containerCapacities":[3,7]}
Output:10
Explanation: We can put item with weight 1 and item with weight 2 into container 1 (capacity 3). This fills container 1 with weight 3. We can put item with weight 3 and item with weight 4 into container 2 (capacity 7). This fills container 2 with weight 7. Total weight transported is 3 + 7 = 10. Items transported: 4. Item with weight 5 cannot be placed.
Example 2:
Input:{"itemWeights":[10,20,30],"containerCapacities":[25,15]}
Output:30
Explanation: We can put item with weight 10 into container 2 (capacity 15). We can put item with weight 20 into container 1 (capacity 25). Total weight transported is 10 + 20 = 30. Items transported: 2. Item with weight 30 cannot be placed.
Example 3:
Input:{"itemWeights":[5,5,5],"containerCapacities":[4,4]}
Output:0
Explanation: No item can fit into any container, so 0 total weight is transported.
Constraints
- 1 <= itemWeights.length <= 1000
- 1 <= containerCapacities.length <= 1000
- 1 <= itemWeights[i] <= 1000
- 1 <= containerCapacities[j] <= 1000
Time: O(N log N + M log M + N*M) Space: O(N + M)
Sort both the item weights and container capacities in ascending order. Iterate through the sorted containers. For each container, iterate through the sorted items and greedily assign the smallest available item that fits into the container's remaining capacity. Mark assigned items to avoid reusing them. This approach ensures that smaller items are prioritized for smaller containers, maximizing the chances of fitting more items overall.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
def distribute_items_into_containers(item_weights: list[int], container_capacities: list[int]) -> int:
item_weights.sort()
container_capacities.sort()
total_weight_transported = 0
item_idx = 0
container_idx = 0
# To maximize the number of items, we should try to fit the smallest items first.
# And use the smallest containers that can fit the current smallest item.
while item_idx < len(item_weights) and container_idx < len(container_capacities):
if item_weights[item_idx] <= container_capacities[container_idx]:
total_weight_transported += item_weights[item_idx]
container_capacities[container_idx] -= item_weights[item_idx] # This line is not actually needed for the problem statement, but good for understanding state
item_idx += 1
container_idx += 1 # Move to the next container after successfully placing an item
else:
# If the current item doesn't fit in the current container, try the next larger container.
container_idx += 1
# Note: We don't increment item_idx here because the current item hasn't been placed yet.
return total_weight_transported