Frontend School

Service Bag Packing

DSA
easy

Service Bag Packing

Easy
Dynamic Programming
Knapsack
Arrays

Overview

At Urban Company, our service technicians often carry a toolkit or bag containing various items needed for their appointments. To ensure efficiency and comfort, each technician's bag has a maximum weight capacity. It's crucial to optimize what goes into the bag: technicians need to carry as many essential items as possible without exceeding the weight limit. This problem models a simplified version of this real-world packing challenge.

What you need to do / Task

Implement a function maxItemsInBag that determines the maximum number of distinct items a service technician can carry in their bag, given a list of item weights and the bag's total weight capacity. Each item can be taken at most once.

Input & output

Your function will receive the following parameters:

  • itemWeights: An array of numbers (number[]) representing the weight of each available item.
  • bagCapacity: A number (number) representing the maximum total weight the bag can hold.

The function should return a single number (number) which is the maximum count of items that can be packed into the bag without exceeding bagCapacity.

Clarifications

  • If no items can be taken (e.g., all items are heavier than the bag capacity), the function should return 0.
  • All itemWeights[i] and bagCapacity will be positive integers.

Examples

1

Example 1

Input:

itemWeights = [1, 2, 3], bagCapacity = 3

Output:

2

Note:

With a capacity of 3, the technician can take items with weights [1, 2] for a total of 2 items and a total weight of 3. Taking just item [3] would be 1 item. The maximum is 2.

2

Example 2

Input:

itemWeights = [10, 20, 5], bagCapacity = 8

Output:

1

Note:

Only the item with weight 5 can be taken. The items with weights 10 and 20 are too heavy. So, 1 item is the maximum.

3

Example 3

Input:

itemWeights = [2, 3, 5], bagCapacity = 7

Output:

2

Note:

The technician can take items with weights [2, 5] for a total of 2 items and a total weight of 7. Taking [2, 3] gives 2 items with weight 5. The maximum is 2.

4

Example 4

Input:

itemWeights = [1, 1, 1, 1], bagCapacity = 2

Output:

2

Note:

Each '1' represents a distinct item. The technician can take any two items of weight 1, resulting in 2 items and a total weight of 2.

Constraints

Constraints & assumptions

  • 1 <= itemWeights.length <= 100
  • 1 <= itemWeights[i] <= 1000
  • 1 <= bagCapacity <= 10000
  • All input numbers are integers.

What interviewers evaluate

  • Correctness of the dynamic programming approach to solve the 0/1 Knapsack variant.
  • Ability to handle edge cases, such as an empty bag capacity or items that are too heavy.
  • Optimal time and space complexity for the given constraints.
  • Cleanliness, readability, and structure of the code.

Loading editor...