The “Capacity To Ship\u00a0Packages Within\u00a0D Days” problem\u00a0is a classic\u00a0binary search\u00a0question that\u00a0helps you practice\u00a0optimization\u00a0with constraints. <\/p>\n\n\n\n
In this blog, we\u2019ll explain\u00a0the problem, walk\u00a0you through both\u00a0brute force and\u00a0optimal solutions, and make everything\u00a0easy to understand\u00a0with code comments, dry runs, and\u00a0clear explanations.<\/p>\n\n\n\n
Here’s the [Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n\n You are given an array Input:<\/strong> Output:<\/strong> Explanation:<\/strong> Input:<\/strong> Output:<\/strong> Explanation:<\/strong> Let\u2019s solve the problem in the most straightforward way:<\/p>\n\n\n\n This approach is easy to understand but not efficient for large inputs.<\/p>\n\n\n\n
\n\n\n\nProblem Statement<\/strong><\/h2>\n\n\n\n
weights<\/code> where each element represents the weight of a package. You have D<\/code> days to ship all the packages.
You must ship the packages in order (no reordering). Each day, you can ship as many packages as you want, as long as their total weight does not exceed the ship’s capacity.
Your task is to find the minimum ship capacity<\/strong> needed to ship all packages within D<\/code> days.<\/p>\n\n\n\nExample 1<\/strong><\/h3>\n\n\n\n
weights = [1], D = 5<\/code><\/p>\n\n\n\n15<\/code><\/p>\n\n\n\n
A capacity of 15 allows the packages to be shipped in 5 days.<\/p>\n\n\n\nExample 2<\/strong><\/h3>\n\n\n\n
weights = [1], D = 3<\/code><\/p>\n\n\n\n6<\/code><\/p>\n\n\n\n
A capacity of 6 allows the packages to be shipped in 3 days.<\/p>\n\n\n
\n\n\n\nBrute Force Solution (Try Every Possible Capacity)<\/h2>\n\n\n\n
Intuition and Approach<\/h3>\n\n\n\n
\n
Try every possible ship capacity from the maximum single package weight to the sum of all package weights.<\/li>\n\n\n\n
For each capacity, simulate the shipping process and count how many days it would take.<\/li>\n\n\n\n
The first capacity for which the total days is less than or equal to\u00a0D<\/code>\u00a0is our answer.<\/li>\n\n\n\n
We check every possible capacity, so we\u2019re sure to find the minimum one that works.<\/li>\n<\/ol>\n\n\n\nCode Implementation<\/h3>\n\n\n\n