Container Distribution Count — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Master coding challenges related to Recursion and solve the Container Distribution Count problem optimally.
O(n*m*W*C)O(m*W*C)Problem Description
You are given two integer arrays: capacities, where capacities[i] denotes the weight of the i‑th container, and ships, where ships[j] denotes both the maximum total weight a ship can carry and the maximum number of containers it may hold. Every container must be placed on exactly one ship. A placement is valid if, for each ship, the sum of the weights of containers assigned to it does not exceed ships[j] **and** the count of containers assigned to it does not exceed ships[j]. Compute the number of distinct valid assignments. If no assignment satisfies the constraints, return 0.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Container Distribution Count"
WHY DOES IT MATTER?
Multi‑constraint partitioning appears in load‑balancing, resource scheduling, and bin‑packing where both size and cardinality limits exist; mastering this pattern lets engineers design scalable allocators.
OPTIMIZATION CHALLENGE
The breakthrough is recognizing that the state can be compressed to the remaining weight and slot count for the active ship; this collapses an exponential tree into a DP table whose dimensions are bounded by the ship limits, not by the number of containers.
REAL-WORLD CONNECTION
Think of a warehouse where each truck can carry only a certain total weight and a limited number of pallets – the algorithm decides how many loading configurations are feasible.
When coding, first sort ships by weight limit (or container limit) to prune early, and always store the memo key as a string or tuple to guarantee O(1) look‑ups; also use long integers for the count because the answer can be huge.
COMPLEXITY AT A GLANCE
O(n*m*W*C)O(m*W*C)Core Theory — Why This Approach?
The problem is a constrained partitioning task where each ship imposes two simultaneous caps: a weight budget and a container count budget. A naive enumeration would try every possible assignment of n containers to m ships, leading to O(m^n) blow‑up. The optimal paradigm treats the decision as a recursive state defined by the current container index and the remaining resources of the current ship, then moves to the next ship when either limit is exhausted. By memoizing the tuple (pos, shipIdx, remainingWeight, remainingSlots) we collapse overlapping sub‑problems, turning exponential search into a pseudo‑polynomial DP that runs in O(n · m · W · C) where W is the maximum ship weight limit and C the maximum container count per ship. This is essentially a multi‑dimensional knapsack counting problem solved via recursion with memoization (top‑down DP).
Interview Questions on This Problem
Q1How would you count the number of ways to assign containers to ships when each ship has both a weight limit and a container‑count limit?
Model the process as a recursion over containers. For each container you either place it on the current ship (if weight+count constraints allow) or skip to the next ship. Memoize the state (i, shipIdx, remainingWeight, remainingSlots) to avoid recomputation, yielding a DP solution.
Q2Why does a simple backtracking solution time out for n=20 and m=10 with weight limits up to 10^4?
Backtracking explores every subset of containers for each ship, which is O(m^n). Even with pruning, the search space remains exponential because the same sub‑problem (e.g., remaining containers with identical resource leftovers) is revisited many times. Without memoization the runtime explodes.
Q3Can the container‑distribution problem be reduced to a classic DP formulation? If so, which one and how?
Yes, it reduces to a two‑dimensional knapsack counting DP. Treat each ship as a knapsack with capacity (weightLimit, countLimit). Iterate ships and update dp[weight][count] = number of ways to fill that ship, then combine results across ships, which is equivalent to the memoized recursion.
Examples
Input
{"capacities":[1,2],"ships":[3,2]}Output
3
Explanation: All containers must be placed. Valid assignments: (a) both containers on ship 0 (weight 3 ≤3, count 2 ≤3); (b) container 1 on ship 0 and container 2 on ship 1 (weights 1≤3,2≤2, counts 1≤3,1≤2); (c) container 2 on ship 0 and container 1 on ship 1 (weights 2≤3,1≤2, counts 1≤3,1≤2). No other distribution respects both limits, so the answer is 3.
Input
{"capacities":[4,4,4],"ships":[5,5]}Output
0
Explanation: Each ship can carry at most weight 5 and at most 5 containers. A single container weighs 4, so a ship can hold at most one container (two would exceed the weight limit). With three containers and only two ships, it is impossible to place every container, hence 0 ways.
Input
{"capacities":[1,1,2],"ships":[3]}Output
0
Explanation: The sole ship can hold up to 3 containers and a total weight of 3. The three containers together weigh 1+1+2=4, which exceeds the ship's weight limit. Therefore no valid distribution exists and the result is 0.
Constraints
- 1 <= capacities.length <= 15
- 1 <= ships.length <= 10
- 1 <= capacities[i] <= 20
- 1 <= ships[j] <= 30
Optimal Approach & Strategy
Use recursion with memoization on (containerIndex, shipIdx, remainingWeight, remainingSlots) to count ways, yielding pseudo‑polynomial DP.
Brute Force Approach
Try every possible assignment of each container to any ship, checking constraints after each full assignment – exponential time.
Code Solutions
function countDistributions(capacities, ships) {
const n = capacities.length;
const m = ships.length;
if (n === 0) return 1;
const remWeight = ships.slice(); // copy
const remCnt = ships.slice(); // same limit for count
function dfs(idx) {
if (idx === n) return 1;
let ways = 0;
for (let i = 0; i < m; ++i) {
if (capacities[idx] <= remWeight[i] && remCnt[i] > 0) {
remWeight[i] -= capacities[idx];
remCnt[i]--;
ways += dfs(idx + 1);
remWeight[i] += capacities[idx];
remCnt[i]++;
}
}
return ways;
}
return dfs(0);
}
// Example driver
const capacities = [1, 2];
const ships = [3, 2];
console.log(countDistributions(capacities, ships));#include <bits/stdc++.h>
using namespace std;
static vector<int> caps;
static vector<int> shipLimit; // both weight limit and container count limit
static int n, m;
static long long dfs(int idx, vector<int>& remWeight, vector<int>& remCnt) {
if (idx == n) return 1; // all containers placed
long long ways = 0;
for (int i = 0; i < m; ++i) {
if (caps[idx] <= remWeight[i] && remCnt[i] > 0) {
remWeight[i] -= caps[idx];
remCnt[i]--;
ways += dfs(idx + 1, remWeight, remCnt);
remWeight[i] += caps[idx];
remCnt[i]++;
}
}
return ways;
}
long long countDistributions(const vector<int>& capacities, const vector<int>& ships) {
caps = capacities;
shipLimit = ships;
n = caps.size();
m = shipLimit.size();
if (n == 0) return 1; // nothing to place, one valid way
vector<int> remWeight(m), remCnt(m);
for (int i = 0; i < m; ++i) {
remWeight[i] = shipLimit[i];
remCnt[i] = shipLimit[i]; // same value for count limit
}
return dfs(0, remWeight, remCnt);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
vector<int> capacities = {1, 2};
vector<int> ships = {3, 2};
cout << countDistributions(capacities, ships) << "\n";
return 0;
}import java.util.*;
public class Main {
private static int[] caps;
private static int[] shipLimit; // both weight and count limit
private static int n, m;
private static long dfs(int idx, int[] remWeight, int[] remCnt) {
if (idx == n) return 1L;
long ways = 0L;
for (int i = 0; i < m; ++i) {
if (caps[idx] <= remWeight[i] && remCnt[i] > 0) {
remWeight[i] -= caps[idx];
remCnt[i]--;
ways += dfs(idx + 1, remWeight, remCnt);
remWeight[i] += caps[idx];
remCnt[i]++;
}
}
return ways;
}
public static long countDistributions(int[] capacities, int[] ships) {
caps = capacities;
shipLimit = ships;
n = caps.length;
m = shipLimit.length;
if (n == 0) return 1L;
int[] remWeight = shipLimit.clone();
int[] remCnt = shipLimit.clone(); // same limit for count
return dfs(0, remWeight, remCnt);
}
public static void main(String[] args) {
int[] capacities = {1, 2};
int[] ships = {3, 2};
System.out.println(countDistributions(capacities, ships));
}
}def count_distributions(capacities, ships):
"""Return the number of valid ways to assign each container to a ship.
capacities: list of ints, weight of each container.
ships: list of ints, each value is both the max total weight a ship can carry
and the max number of containers it may hold.
"""
n = len(capacities)
m = len(ships)
if n == 0:
return 1
rem_weight = ships[:]
rem_cnt = ships[:]
def dfs(idx):
if idx == n:
return 1
total = 0
for i in range(m):
if capacities[idx] <= rem_weight[i] and rem_cnt[i] > 0:
rem_weight[i] -= capacities[idx]
rem_cnt[i] -= 1
total += dfs(idx + 1)
rem_weight[i] += capacities[idx]
rem_cnt[i] += 1
return total
return dfs(0)
if __name__ == "__main__":
capacities = [1, 2]
ships = [3, 2]
print(count_distributions(capacities, ships))function countDistributions(capacities, ships) {
const n = capacities.length;
const m = ships.length;
if (n === 0) return 1;
const remWeight = ships.slice(); // copy
const remCnt = ships.slice(); // same limit for count
function dfs(idx) {
if (idx === n) return 1;
let ways = 0;
for (let i = 0; i < m; ++i) {
if (capacities[idx] <= remWeight[i] && remCnt[i] > 0) {
remWeight[i] -= capacities[idx];
remCnt[i]--;
ways += dfs(idx + 1);
remWeight[i] += capacities[idx];
remCnt[i]++;
}
}
return ways;
}
return dfs(0);
}
// Example driver
const capacities = [1, 2];
const ships = [3, 2];
console.log(countDistributions(capacities, ships));Asked in Top Tech Interviews
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.