Capacity to Ship Packages in D Days
Ramayana — Hanuman's Cargo Ship — Minimum Carrying Capacity to Deliver All in D Days
d दिनों में सभी बोझ — न्यूनतम क्षमता क्या?। एक-एक बोझ क्रम से — पूर्ण होने पर नया दिन॥
*All loads in d days — what minimum capacity? Load items one by one in order — start a new day when full.*
The Story
Packages must be shipped in order (no rearranging). A ship with capacity `cap` can ship packages on a single day until the total weight exceeds cap, then starts a new day. Find the minimum capacity to ship all packages within d days.
For `weights=[1,2,3,4,5,6,7,8,9,10]`, d=5: answer=15.
**Binary search on capacity:** - lo = max(weights) (must fit at least the heaviest package) - hi = sum(weights) (ship everything in one day) - Feasibility: greedy pack on current day; when can't add more → new day
```java boolean canShip(int[] weights, int days, int cap) { int daysNeeded=1, currentLoad=0; for (int w : weights) { if (currentLoad + w > cap) { daysNeeded++; currentLoad=0; } currentLoad += w; } return daysNeeded <= days; } ```
This is the same minimize-template as bs-11 (Koko). canShip is monotone: larger cap → fewer days needed.
The Incremental Capacity Finder
Try capacity from max(weights) upward. Return first feasible capacity. O(n × sum).
public int shipBruteForce(int[] weights, int days) {
int max=0, sum=0;
for (int w : weights) { max=Math.max(max,w); sum+=w; }
for (int c=max; c<=sum; c++) {
int d=1, load=0;
for (int w : weights) { if(load+w>c){d++;load=0;} load+=w; }
if (d<=days) return c;
}
return -1;
}Hanuman's Minimum-Capacity Wisdom
public int shipWithinDays(int[] weights, int days) {
int lo = 0, hi = 0;
for (int w : weights) { lo = Math.max(lo, w); hi += w; }
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
int daysNeeded = 1, load = 0;
for (int w : weights) {
if (load + w > mid) { daysNeeded++; load = 0; }
load += w;
}
if (daysNeeded <= days) hi = mid;
else lo = mid + 1;
}
return lo;
}Step-by-Step Walkthrough
[1,2,3,4,5], d=5 lo=5,hi=15 mid=10: greedy: 1+2+3+4=10✓,5=5✓ → 2 days ≤5 → hi=10 mid=7: 1+2+3=6✓+4>7→new day,4+5>7→new day(only 4),5=5✓ → 4 days ≤5 → hi=7 ...converges to 5 ✅
Deep Insight
**Pattern family:** bs-11 (Koko), bs-12 (Bouquets), bs-16 (Ship), bs-17 (Book Allocation), bs-18 (Split Array) — all are the SAME minimize template: - lo=lower bound (minimum feasible) - hi=upper bound (trivially feasible) - Feasible: hi=mid; Infeasible: lo=mid+1 - Return lo
**Packages must be in ORDER.** Unlike the bin-packing problem, we cannot rearrange. The greedy check simply loads in order, starting a new day when overloaded.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n × sum) | O(1) | Try each capacity |
| Optimal | O(n log sum) | O(1) | Binary search on [max,sum] + O(n) check |
Pattern Recognition
✅ Minimize capacity to ship in d days ✅ Same template as Koko, Book Allocation, Split Array ✅ Feasible: hi=mid; Infeasible: lo=mid+1; return lo ✅ lo=max(weights), hi=sum(weights) **LeetCode Trigger Phrases:** → "ship packages within D days" → "minimum capacity" for ordered partition → Order-preserving partition minimum
Bhagavad Gita 16.16
अनेकचित्तविभ्रान्तान्मोहजालसमावृतान्। प्रसक्तान्कामभोगेषु पतन्ति नरकेऽशुचौ॥
Those deluded by many distracting thoughts, covered by the net of delusion, excessively attached to sense pleasures — they fall into impure hell.
Connection: The ship loads packages one by one, in order, never rearranging — disciplined sequential commitment. The capacity represents the ship's limits of dharma; exceeding it forces a new day (new beginning). Like the contrast between disciplined action and the chaos of excessive desire, the algorithm finds the minimum discipline (capacity) needed to complete the journey in the allotted time, neither over-burdened nor under-utilized.