Optimal Package Consolidation Path
Shiprocket operates large-scale sorting and consolidation facilities. Optimizing the flow of packages through these facilities is critical for efficiency and profitability. This problem simulates a scenario where a package consolidation robot needs to navigate a grid-based sorting area, picking up packages, while adhering to a strict total weight limit to prevent equipment overload or delays.
Implement the function maxConsolidatedValue that determines the maximum total value of packages that can be collected along a valid path from the top-left cell (0, 0) to the bottom-right cell (R-1, C-1) of a given grid. You can only move right or down at each step.
Each cell (r, c) in the grid contains a package object with two properties: value (representing the profit or priority of the package) and weight (representing its physical weight or handling complexity). The total weight of all packages collected along any path must not exceed maxCapacity.
Input:
grid: A 2D array (matrix) where grid[r][c] is an object { value: number, weight: number } representing the package at cell (r, c). R is the number of rows, C is the number of columns.maxCapacity: A number representing the maximum total weight allowed for a path.Output:
number representing the maximum total value of packages collected along a valid path. If no path exists that reaches the bottom-right cell within the maxCapacity, return 0.value and weight properties of packages are positive integers.(0,0) and the ending cell (R-1, C-1) are always included in the path and their respective package values and weights contribute to the total.maxCapacity is too low such that even the first package at (0,0) exceeds it, then no path can start, and the result should be 0 (as per the rule for no valid path).Examples
Example 1
Input:
grid = [[{ value: 10, weight: 1 }, { value: 5, weight: 1 }], [{ value: 20, weight: 1 }, { value: 10, weight: 1 }]], maxCapacity = 3
Output:
40
Note:
Grid: [10,1] [5,1] [20,1] [10,1]
Path 1: (0,0) -> (0,1) -> (1,1) Value: 10 + 5 + 10 = 25 Weight: 1 + 1 + 1 = 3. Valid (3 <= 3).
Path 2: (0,0) -> (1,0) -> (1,1) Value: 10 + 20 + 10 = 40 Weight: 1 + 1 + 1 = 3. Valid (3 <= 3).
Maximum value is 40.
Example 2
Input:
grid = [[{ value: 10, weight: 2 }, { value: 100, weight: 1 }], [{ value: 1, weight: 10 }, { value: 5, weight: 1 }]], maxCapacity = 4
Output:
115
Note:
Grid: [10,2] [100,1] [1,10] [5,1]
Path 1: (0,0) -> (0,1) -> (1,1) Value: 10 + 100 + 5 = 115 Weight: 2 + 1 + 1 = 4. Valid (4 <= 4).
Path 2: (0,0) -> (1,0) -> (1,1) Value: 10 + 1 + 5 = 16 Weight: 2 + 10 + 1 = 13. Invalid (13 > 4).
Maximum value is 115.
Example 3
Input:
grid = [[{ value: 10, weight: 5 }]], maxCapacity = 3
Output:
0
Note:
The grid is 1x1. The package at (0,0) has weight 5. The maxCapacity is 3. Since the initial package's weight already exceeds the capacity, no path is valid. Returns 0.
Constraints
1 <= R, C <= 50 (number of rows and columns)1 <= grid[r][c].value <= 1001 <= grid[r][c].weight <= 201 <= maxCapacity <= 1000O(R * C * maxCapacity)).O(R * C * maxCapacity)).maxCapacity constraint, including proper initialization and invalid state handling.Loading editor...