mediumDynamic ProgrammingPattern: DP
Minimum Cost Item Distribution with Capacity Solution
Problem Statement
You are given `numCategories` categories, where each category has a maximum capacity of `maxCapacity` items. You need to distribute exactly `totalItems` items across these `numCategories`. The cost of placing `j` items into category `i` is given by a 2D array `costMatrix`, where `costMatrix[i][j]` represents this cost. Your task is to find the minimum total cost to distribute `totalItems` items such that the number of items placed in any single category does not exceed `maxCapacity`.
Examples
Example 1:
Input:numCategories = 2, maxCapacity = 3, totalItems = 4, costMatrix = [[0, 10, 20, 30], [0, 5, 12, 25]]
Output:32
Explanation: We need to distribute 4 items across 2 categories, each with a maximum capacity of 3 items.
Possible distributions (items in Category 0, items in Category 1):
- (1, 3): Cost = costMatrix[0][1] + costMatrix[1][3] = 10 + 25 = 35
- (2, 2): Cost = costMatrix[0][2] + costMatrix[1][2] = 20 + 12 = 32
- (3, 1): Cost = costMatrix[0][3] + costMatrix[1][1] = 30 + 5 = 35
The minimum total cost is 32.
Example 2:
Input:numCategories = 1, maxCapacity = 5, totalItems = 3, costMatrix = [[0, 10, 20, 30, 40, 50]]
Output:30
Explanation: There is only one category, so all 3 items must be placed in Category 0. The cost is costMatrix[0][3] = 30.
Constraints
- `1 <= numCategories <= 30`
- `0 <= maxCapacity <= 20`
- `0 <= totalItems <= numCategories * maxCapacity`
- `0 <= costMatrix[i][j] <= 1000`
- `costMatrix` will always have `numCategories` rows and `maxCapacity + 1` columns, where `costMatrix[i][0]` is guaranteed to be 0 for all `i`.
Time: O(numCategories * totalItems * maxCapacity) Space: O(numCategories * totalItems)
This problem is best solved using dynamic programming. We define `dp[i][j]` as the minimum cost to distribute `j` items among the first `i` categories. The state transition involves iterating through the number of items `k` (from `0` to `maxCapacity`) placed in the `i`-th category, adding `costMatrix[i-1][k]` to `dp[i-1][j-k]`, and taking the minimum over all valid `k` to compute `dp[i][j]`. This approach ensures each subproblem is solved only once.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
import sys
def read_input():
return sys.stdin.readline().strip()
num_categories, max_capacity, total_items = map(int, read_input().split())
cost_matrix = []
for _ in range(num_categories):
cost_matrix.append(list(map(int, read_input().split())))
inf = float("inf")
dp = [[inf] * (total_items + 1) for _ in range(num_categories + 1)]
dp[0][0] = 0
for i in range(1, num_categories + 1):
for j in range(total_items + 1):
for k in range(min(j, max_capacity) + 1):
dp[i][j] = min(dp[i][j], dp[i - 1][j - k] + cost_matrix[i - 1][k])
print(dp[num_categories][total_items])