Capacity To Ship Packages Within D Days | C ++ program for the above approach ; Function to check if the weights can be delivered in D days or not ; Stores the count of days required to ship all the weights if the maximum capacity is mx ; Traverse all the weights ; If total weight is more than the maximum capacity ; If days are more than D , then return false ; Return true for the days < D ; Function to find the least weight capacity of a boat to ship all the weights within D days ; Stores the total weights to be shipped ; Find the sum of weights ; Stores the maximum weight in the array that has to be shipped ; Store the ending value for the search space ; Store the required result ; Perform binary search ; Store the middle value ; If mid can be shipped , then update the result and end value of the search space ; Search for minimum value in the right part ; Print the result ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool isValid ( int weight [ ] , int n , int D , int mx ) { int st = 1 ; int sum = 0 ; for ( int i = 0 ; i < n ; i ++ ) { sum += weight [ i ] ; if ( sum > mx ) { st ++ ; sum = weight [ i ] ; } if ( st > D ) return false ; } return true ; } void shipWithinDays ( int weight [ ] , int D , int n ) { int sum = 0 ; for ( int i = 0 ; i < n ; i ++ ) sum += weight [ i ] ; int s = weight [ 0 ] ; for ( int i = 1 ; i < n ; i ++ ) { s = max ( s , weight [ i ] ) ; } int e = sum ; int res = -1 ; while ( s <= e ) { int mid = s + ( e - s ) / 2 ; if ( isValid ( weight , n , D , mid ) ) { res = mid ; e = mid - 1 ; } else s = mid + 1 ; } cout << res ; } int main ( ) { int weight [ ] = { 9 , 8 , 10 } ; int D = 3 ; int N = sizeof ( weight ) / sizeof ( weight [ 0 ] ) ; shipWithinDays ( weight , D , N ) ; return 0 ; }