BackmediumBacktracking Accenture

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.

Example 1

Input

{"itemWeights":[1,2,3,4,5],"containerCapacities":[3,7]}

Output

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

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

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

Distribute Items into Containers Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Constraints

More Backtracking Problems

Optimized Approach

Step-by-Step Dry Run

Tested Solutions