BackmediumBacktrackinguncategorizedmedium

Maximum Subset with Three Resource Constraints Solution

Problem Statement

You are managing a production line with three distinct raw material types, denoted as Type A, Type B, and Type C. You have a finite inventory of these materials, specified by the integers limitA, limitB, and limitC. A list of n production orders is available, where each order i requires a specific quantity of each material type, represented by the array order[i] = [reqA_i, reqB_i, reqC_i].

Your objective is to determine the maximum number of orders that can be fully processed. An order is considered processed only if the cumulative consumption of Type A, Type B, and Type C materials across all selected orders does not exceed their respective inventory limits. You may select any subset of the orders, but the total resource usage for each type must remain within the provided bounds.

Return the maximum count of orders that can be satisfied under these constraints.

Example 1
Input
limitA = 10, limitB = 10, limitC = 10 orders = [[2, 3, 4], [5, 5, 5], [1, 1, 1], [4, 4, 4]]
Output
3

Explanation: We can select orders 0, 2, and 3. Total A: 2 + 1 + 4 = 7 (<= 10) Total B: 3 + 1 + 4 = 8 (<= 10) Total C: 4 + 1 + 4 = 9 (<= 10) If we try to add order 1, Total A becomes 12, which exceeds the limit. Thus, the maximum is 3.

Example 2
Input
limitA = 5, limitB = 5, limitC = 5 orders = [[5, 0, 0], [0, 5, 0], [0, 0, 5], [1, 1, 1]]
Output
3

Explanation: Selecting orders 0, 1, and 2 uses exactly 5 units of each resource. Total A: 5 + 0 + 0 = 5 Total B: 0 + 5 + 0 = 5 Total C: 0 + 0 + 5 = 5 Adding order 3 would exceed all limits. Hence, the answer is 3.

Example 3
Input
limitA = 100, limitB = 100, limitC = 100 orders = [[10, 10, 10], [10, 10, 10], [10, 10, 10], [10, 10, 10], [10, 10, 10]]
Output
5

Explanation: Each order consumes 10 units of every resource. Total for 5 orders: A=50, B=50, C=50. All are within the limit of 100. Since there are only 5 orders, the maximum possible is 5.

Constraints

  • 1 <= n <= 100
  • 1 <= limitA, limitB, limitC <= 10^4
  • 1 <= reqA_i, reqB_i, reqC_i <= 10^3
  • The sum of reqA_i for all i is <= 10^4
  • The sum of reqB_i for all i is <= 10^4
  • The sum of reqC_i for all i is <= 10^4

More Backtracking

Protocol Tome Tracker 4easyNode Matrix Optimizer 8easyNetwork Node Architect 13easyProtocol Pipeline Detector 18easyNode Payload Analyzer 23easyNetwork Network Extractor 28easyProtocol Sensor Evaluator 32easyNode Vault Aligner 37easy
View all problems →
Live Compiler1 Free Run Available
Loading Editor...
Test Cases & Output
Click "Run" to test your 1 free compile trial!

🚀 Practice this problem

Run code, get AI hints & track streak

Sign Up Free

Maximum Subset with Three Resource Constraints — Problem Statement & Solution Guide

BacktrackingMediumMixed
TimeO(n * limitA * limitB * limitC)
|
SpaceO(limitA * limitB * limitC) (or O(limitA * limitB) with rolling array)

Problem Description

You are managing a production line with three distinct raw material types, denoted as Type A, Type B, and Type C. You have a finite inventory of these materials, specified by the integers limitA, limitB, and limitC. A list of n production orders is available, where each order i requires a specific quantity of each material type, represented by the array order[i] = [reqA_i, reqB_i, reqC_i].

Your objective is to determine the maximum number of orders that can be fully processed. An order is considered processed only if the cumulative consumption of Type A, Type B, and Type C materials across all selected orders does not exceed their respective inventory limits. You may select any subset of the orders, but the total resource usage for each type must remain within the provided bounds.

Return the maximum count of orders that can be satisfied under these constraints.

DSA Pattern Breakdown

DSA Pattern Breakdown

"Maximum Subset with Three Resource Constraints"

medium

WHY DOES IT MATTER?

Multi‑dimensional knapsack patterns appear whenever a system must respect several independent quotas—budget, memory, and latency, for example. Mastering this pattern equips engineers to design resource‑aware schedulers, admission controllers, and capacity planners.

OPTIMIZATION CHALLENGE

The key insight is that the DP transition only needs the previous layer, enabling a rolling array that collapses one dimension. Recognising this reduces memory from cubic to quadratic, making the solution viable for typical interview limits (≤ 100 each).

REAL-WORLD CONNECTION

Think of a cloud orchestrator that must allocate CPU cores, RAM, and GPU units to incoming jobs. Each job consumes a triple of resources, and the orchestrator wants to admit the maximum number of jobs without exceeding any quota—exactly the three‑resource knapsack.

During coding, initialise the DP array with -∞ (or a sentinel) except DP[0][0][0] = 0, and always iterate resource loops backwards. This prevents re‑using the same order multiple times and eliminates subtle off‑by‑one bugs.

COMPLEXITY AT A GLANCE

⏱ Time:O(n * limitA * limitB * limitC)
💾 Space:O(limitA * limitB * limitC) (or O(limitA * limitB) with rolling array)

Core Theory — Why This Approach?

The problem is a classic 0/1 multi‑dimensional knapsack where each order is an item with three weights (reqA, reqB, reqC) and a uniform profit of 1. A naive exhaustive search would enumerate all 2ⁿ subsets, which explodes even for moderate n. The optimal paradigm is dynamic programming that builds a state table DP[a][b][c] = maximum number of orders that can be fulfilled using at most a units of A, b units of B, and c units of C. By iterating over orders and updating the table in reverse (to preserve 0/1 semantics), we guarantee that each order is considered exactly once, turning exponential combinatorics into a pseudo‑polynomial solution bounded by the product of the three limits. Further refinements—such as rolling the three‑dimensional array into two layers or compressing one dimension with a bitset—shrink memory from O(limitA·limitB·limitC) to O(limitA·limitB) while preserving the same time bound.

Interview Questions on This Problem

Q1How would you adapt the 0/1 knapsack DP to handle three independent resource constraints while still maximizing the count of selected orders?

Create a 3‑D DP array DP[a][b][c] storing the maximum number of orders achievable with resources a, b, c. Iterate over each order and update the array in reverse for all a ≥ reqA, b ≥ reqB, c ≥ reqC: DP[a][b][c] = max(DP[a][b][c], DP[a‑reqA][b‑reqB][c‑reqC] + 1). Finally, the answer is DP[limitA][limitB][limitC].

Q2What space‑optimisation technique can you apply to the three‑dimensional DP, and why does it work?

Since each transition only depends on the previous layer (the state before processing the current order), we can keep two 2‑D slices: current and previous. After processing an order we swap the slices. This reduces space from O(limitA·limitB·limitC) to O(limitA·limitB) because the C dimension is folded into the value stored (the maximum count) for each (a,b) pair.

Q3In a scenario where limitA, limitB, and limitC are each up to 10⁴, the O(limit³) DP is infeasible. Which alternative algorithmic strategy could you propose?

Use a meet‑in‑the‑middle approach: split the orders into two halves, enumerate all feasible subsets of each half (pruning those exceeding any limit), and store for each subset its total resource usage and order count. Then sort one list and for each entry in the other, binary‑search the best compatible entry respecting the remaining capacities. This runs in O(2^{n/2}) time and handles large limits at the cost of exponential dependence on n, which is acceptable when n ≤ 30‑40.

Examples

Example 1

Input

limitA = 10, limitB = 10, limitC = 10
orders = [[2, 3, 4], [5, 5, 5], [1, 1, 1], [4, 4, 4]]

Output

3

Explanation: We can select orders 0, 2, and 3. Total A: 2 + 1 + 4 = 7 (<= 10) Total B: 3 + 1 + 4 = 8 (<= 10) Total C: 4 + 1 + 4 = 9 (<= 10) If we try to add order 1, Total A becomes 12, which exceeds the limit. Thus, the maximum is 3.

Example 2

Input

limitA = 5, limitB = 5, limitC = 5
orders = [[5, 0, 0], [0, 5, 0], [0, 0, 5], [1, 1, 1]]

Output

3

Explanation: Selecting orders 0, 1, and 2 uses exactly 5 units of each resource. Total A: 5 + 0 + 0 = 5 Total B: 0 + 5 + 0 = 5 Total C: 0 + 0 + 5 = 5 Adding order 3 would exceed all limits. Hence, the answer is 3.

Example 3

Input

limitA = 100, limitB = 100, limitC = 100
orders = [[10, 10, 10], [10, 10, 10], [10, 10, 10], [10, 10, 10], [10, 10, 10]]

Output

5

Explanation: Each order consumes 10 units of every resource. Total for 5 orders: A=50, B=50, C=50. All are within the limit of 100. Since there are only 5 orders, the maximum possible is 5.

Constraints

  • 1 <= n <= 100
  • 1 <= limitA, limitB, limitC <= 10^4
  • 1 <= reqA_i, reqB_i, reqC_i <= 10^3
  • The sum of reqA_i for all i is <= 10^4
  • The sum of reqB_i for all i is <= 10^4
  • The sum of reqC_i for all i is <= 10^4

Optimal Approach & Strategy

Use a three‑dimensional DP (or a rolled two‑layer version) that updates states in reverse for each order, achieving pseudo‑polynomial time.

Brute Force Approach

Enumerate every subset of orders, sum their resource usage, and keep the largest subset that stays within all three limits.

Verified Code Solutions

JavaScript Solution
Time: O(n * limitA * limitB * limitC)
function solution(R1, R2, R3, demands) {
      let count = 0;
      let remainingResources = [R1, R2, R3];
      demands.sort((a, b) => a[0] + a[1] + a[2] - b[0] - b[1] - b[2]);
      for (let demand of demands) {
         if (demand[0] <= remainingResources[0] && demand[1] <= remainingResources[1] && demand[2] <= remainingResources[2]) {
            count++;
            remainingResources[0] -= demand[0];
            remainingResources[1] -= demand[1];
            remainingResources[2] -= demand[2];
         }
      }
      return count;
   }

Asked in Top Tech Interviews

uncategorizedmediumnone

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Sign Up & Solve Free →Browse All Problems