Question

UPS is renting trucks to deliver packages for morning and evening shifts. Each zone of the city needs several trucks and those numbers are calculated and given to the manager by midnight on a daily basis. With this data the manager will then rent enough trucks for the morning shift and reuse them for the afternoon shift. Note that each zone must be completely covered in either shift.

For examples, if the city has 4 zones and their truck requirements, in this order, zone #1 needs 1 truck, zone#2 needs 6 trucks, zone#3 needs 11 trucks and zone#4 needs 5 trucks, the manager could rent 16 trucks to deliver packages in zones #3 (11 trucks) and #4 (5 trucks) in the morning shift and reuse 7 trucks to cover zones #1 (1 truck) and #2 (6 trucks) in the afternoon shift but he would need to leave 9 trucks unused for the afternoon shift. Alternatively, the manager could have rented 12 trucks to cover zones #1 (1 truck) and #3 (11 trucks) in the morning and reuse 11 trucks to deliver packages in zones #2 (6 trucks) and #4 (5 trucks). In this plan, he would only have 1 truck left unused. Note that 12 is also the minimum number of trucks needed.

Find the minimum numbers of trucks for daily delivery. Is there an optimal solution? Use any programming language to solve this problem and write a pseudo-code for the procedure. What is the time complexity?

Answer 1

#include <iostream>
using namespace std;

int minDiffSubset(int arr[], int i, int n, int sumCalculated, int sumTotal)
{
if (i==n)
return abs((sumTotal-sumCalculated) - sumCalculated);

return min(minDiffSubset(arr, i+1, n, sumCalculated+arr[i], sumTotal),
minDiffSubset(arr, i+1, n, sumCalculated, sumTotal));
}

int main() {
   int n;
   cin>>n;
   int a[n];
   int sum = 0;
   for(int i=0;i<n;i++) {
       cin>>a[i];
       sum+=a[i];
   }

   int minDiff = minDiffSubset(a, 0, n, 0, sum);

   int ans = (sum + minDiff) / 2;

   cout<<ans<<endl;
}

// Time complexy = O(2^N) where N is the number of zones

/*
Pseudo code
a = list of the number of trucks needed to each zone
n = size of a

for i in 0..n:
   sum = sum + a[i]

Now the problem becomes like partitioning a set into two subsets such that the difference of subset sums is minimum
Recursively find the minimum diff of subset sum using this recursive call

minDiff = min(minDiffSubset(arr, i+1, n, sumCalculated+arr[i], sumTotal),
minDiffSubset(arr, i+1, n, sumCalculated, sumTotal))

Once we find the minDiff the answer will be the (sum + minDiff) / 2

*/

/*
Optimization

This could be optimized by using DP to find the partition of a set into two subsets such that the difference of subset sums is minimum

dp[i][j] = dp[i-1][j] || dp[i-1][j-a[i]];
here dp[i][j] denotes whether j sum is possible using a subset of first i elements

Now since you know if a particular sum is possbile or not, you can check for the minimum sum that is possible and which is grater than sum/2.
Here sum is the sum of all the elements of the array or list.

*/

/*
code with dp

#include <iostream>
using namespace std;

int minTrucksRequired(int a[], int n, int sum)
{
bool dp[n+1][sum+1];

for (int i=0;i<=n;i++) {
        dp[i][0] = true;
}

for(int i=0;i<=sum;i++) {
        dp[0][i] = false;
}

dp[0][0] = true;

for (int i=1;i<=n;i++) {
    for (int j=1;j<=sum;j++) {
        dp[i][j] = dp[i-1][j];
        if (j>=a[i-1]) {
            dp[i][j] = dp[i][j] | dp[i-1][j-a[i-1]];
        }

    }
}

for(int i=0;i<=sum;i++) {
      if (dp[n][i]) {
          cout<<i<<endl;
          if (i*2 >= sum )
          {
             return i;
          }
      }
}
return 0;
}

int main() {
   int n;
   cin>>n;
   int a[n];
   int sum = 0;
   for(int i=0;i<n;i++) {
       cin>>a[i];
       sum+=a[i];
   }

   cout<<minTrucksRequired(a, n, sum);
}
*/