Frontend School

Optimal Warehouse Loading

DSA
medium

Optimal Warehouse Loading

Medium
Dynamic Programming
2D DP
Knapsack
Optimization

Overview

Meesho's logistics team aims to maximize the efficiency of product delivery. Each delivery truck has strict maximum weight and volume capacities. Given a list of various products, each with its own weight, volume, and associated market value, the challenge is to select an optimal subset of products to load into a truck. The goal is to maximize the total value of loaded products while strictly adhering to both the weight and volume constraints of the truck.

What you need to do / Task

Implement a function maxProductLoadingValue that calculates the maximum total value of products that can be loaded into a truck.

Input & output

Function Signature: function maxProductLoadingValue(maxWeight: number, maxVolume: number, products: Product[]): number

Parameters:

  • maxWeight: An integer representing the maximum weight capacity of the truck.
  • maxVolume: An integer representing the maximum volume capacity of the truck.
  • products: An array of objects, where each object represents a product and has the following properties:
    • weight: An integer representing the product's weight.
    • volume: An integer representing the product's volume.
    • value: An integer representing the product's market value.

Return Value:

  • An integer representing the maximum total value of products that can be loaded into the truck without exceeding its maxWeight and maxVolume capacities.

Clarifications

  • Each product can be used at most once (this is a 0/1 Knapsack problem).
  • Products cannot be broken down; they must be taken whole or not at all.
  • If no products can be loaded due to capacity constraints or an empty products list, the maximum value is 0.

Examples

1

Example 1

Input:

maxWeight = 10, maxVolume = 10, products = [{weight: 2, volume: 3, value: 5}, {weight: 3, volume: 4, value: 7}, {weight: 5, volume: 6, value: 10}]

Output:

17

Note:

To maximize value:

  • Product 1 (w:2, v:3, val:5)
  • Product 2 (w:3, v:4, val:7)
  • Product 3 (w:5, v:6, val:10)

Possible combinations within (10,10) capacity:

  • Only Product 1: Value 5 (w:2, v:3)
  • Only Product 2: Value 7 (w:3, v:4)
  • Only Product 3: Value 10 (w:5, v:6)
  • Product 1 + Product 2: Value 12 (w:5, v:7)
  • Product 1 + Product 3: Value 15 (w:7, v:9)
  • Product 2 + Product 3: Value 17 (w:8, v:10)
  • Product 1 + Product 2 + Product 3: Exceeds capacity (w:10, v:13)

The maximum value is 17 (by taking Product 2 and Product 3).

2

Example 2

Input:

maxWeight = 5, maxVolume = 5, products = [{weight: 6, volume: 2, value: 10}, {weight: 2, volume: 6, value: 12}, {weight: 3, volume: 3, value: 7}]

Output:

7

Note:

Given capacities (5,5):

  • Product 1 (w:6, v:2, val:10) exceeds maxWeight.
  • Product 2 (w:2, v:6, val:12) exceeds maxVolume.
  • Product 3 (w:3, v:3, val:7) fits within capacities. Only Product 3 can be loaded, yielding a value of 7.
3

Example 3

Input:

maxWeight = 10, maxVolume = 10, products = []

Output:

0

Note:

With an empty list of products, no items can be loaded, resulting in a total value of 0.

Constraints

Constraints & assumptions

  • 1 <= maxWeight, maxVolume <= 500
  • 0 <= products.length <= 100
  • 1 <= product.weight <= maxWeight
  • 1 <= product.volume <= maxVolume
  • 1 <= product.value <= 1000
  • All input values (maxWeight, maxVolume, product.weight, product.volume, product.value) are integers.

Out of scope

  • Real-time loading optimizations or dynamic adjustments during transit.
  • Complex geometric packing (e.g., fitting irregular shapes).
  • Scenarios involving multiple trucks or product dependencies (e.g., needing product A to take product B).

What interviewers evaluate

  • Correctness of DP State: Ability to identify and define the appropriate 2D DP state for the problem.
  • DP Transitions: Accurate formulation of the recurrence relation, correctly handling the choice of including or excluding each product based on two constraints.
  • Complexity Analysis: Providing an accurate analysis of the time and space complexity of the solution.
  • Code Quality: Writing clear, readable, and maintainable code, including proper handling of edge cases.

Loading editor...