mediumDynamic ProgrammingPattern: DP
Minimum Resource Fulfillment Solution
Problem Statement
You are given a 2D array `resources` of size `n x 3` where each sub-array represents the amount of oxygen, water, and food respectively, and three integers `targetOxygen`, `targetWater`, and `targetFood` representing the target amounts of each resource. Determine the minimum number of sub-arrays to select to meet or exceed the target amounts of each resource.
Examples
Example 1:
Input:{"resources":[[1,2,3],[4,5,6],[7,8,9]],"targetOxygen":10,"targetWater":15,"targetFood":20}
Output:-1
Explanation: Even selecting all three pods results in total resources of [12, 15, 18]. This is insufficient to meet the target food requirement of 20. No other combination of pods can meet all target requirements. Therefore, it is impossible.
Example 2:
Input:{"resources":[[10,20,30],[40,50,60]],"targetOxygen":50,"targetWater":100,"targetFood":150}
Output:-1
Explanation: Selecting both pods yields total resources of [50, 70, 90]. This is insufficient to meet the target water (100) and food (150) requirements. No combination of these pods can meet all target requirements. Therefore, it is impossible.
Constraints
- 1 <= n <= 100
- 1 <= resources[i][j] <= 1000
- 1 <= targetOxygen, targetWater, targetFood <= 1000
- n is the number of sub-arrays in resources
Time: O(N * targetOxygen * targetWater * targetFood) Space: O(targetOxygen * targetWater * targetFood)
An optimal approach uses dynamic programming with a 3D DP table, `dp[o][w][f]`, representing the minimum number of packages required to achieve at least `o` oxygen, `w` water, and `f` food. Initialize `dp[0][0][0]` to zero and all other states to infinity. Iterate through each resource package available; for each package, iterate backwards through the DP states `(o, w, f)` to update `dp[min(targetO, o+res_o)][min(targetW, w+res_w)][min(targetF, f+res_f)] = min(dp[...], dp[o][w][f] + 1)`. The final answer is `dp[targetOxygen][targetWater][targetFood]`. This yields a time complexity of O(N * T_O * T_W * T_F) and space complexity of O(T_O * T_W * T_F).
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
import sys
resources = []
targetOxygen, targetWater, targetFood = 0, 0, 0
n = int(sys.stdin.readline().strip())
for _ in range(n):
resources.append(list(map(int, sys.stdin.readline().strip().split())))
[targetOxygen, targetWater, targetFood] = map(int, sys.stdin.readline().strip().split())
oxygen, water, food = 0, 0, 0
count = 0
resources.sort(key=lambda x: x[0] + x[1] + x[2], reverse=True)
while oxygen < targetOxygen or water < targetWater or food < targetFood:
oxygen += resources[count][0]
water += resources[count][1]
food += resources[count][2]
count += 1
print(count)