Minimize the number of Knapsacks with total weight W required to store Array containing elements greater than W/3

Algorithm

• Sort the entire weights array
• Maintain two pointers start and end for iterating in the sorted Array of weights from both the ends of the Array
• Run a while loop until the start is less than the end, and in each iteration, check if we can include minimum and maximum weight in a single knapsack, then include them and increment the value of final ans 
• If we are not able to include both the weight in a single knapsack, then include the weight with the larger value and increment the final ans count. 
   

Also read, Euclid GCD Algorithm

Code:

#include <bits/stdc++.h>
using namespace std;

// Function to calculate the minimum number of knapsacks required
int minKnapsacks(vector<int>  &weights,int W)
{
    // ans to store the total number of knapsacks
    int ans = 0;

    // Two pointers start and end to iterate from both the ends of array
    int start = 0;
    int end = weights.size() - 1;

    // Sort the array of weights
    sort(weights.begin(), weights.end());

    while (start <= end) {

        // Check if both the elements can be included then include them
        if ( weights[start] +  weights[end] <= W) {

            // Increment the answer
            ans++;
            start++;end--;
        }
        else {

            // Single knapsack will be required to store last element
            end--;
            ans++;
        }
    }
    return ans;
}

int main()
{
    int W = 200;
    vector<int> weights = { 80,120,100,150 };
    cout << minKnapsacks(weights, W);
}

Output:

3

Time Complexity 

O(N*log(N))

The time complexity for the problem "Minimize the number of Knapsacks with total weigh W required to store Array containing elements greater than W/3" is O(N*log(N)) where 'N' is the total size of the input array. Since we are using the inbuilt sort function that will cost us O(N*log(N)) time complexity and after that, we are iterating in the entire Array, which will cost O(N) time, so the total time complexity will be O(N*log(N)) + O(N) which can be interpreted as O(N*log(N)).

Space Complexity 

0(1)

The space complexity for the problem "Minimize the number of Knapsacks with total weigh W required to store Array containing elements greater than W/3" is 0(1) that is constant space since we are not using any extra space in the entire solution.

Check out this array problem - Merge 2 Sorted Arrays

Frequently Asked Questions

1. What is a two-pointer approach?
   We use two pointers to iterate in a single data structure in a particular fashion
    
2. What all sorting algorithms can we use in this question instead of the inbuilt sort?
   We can use merge sort and quick sort if we want to solve this question in o(N*log(N)) time complexity otherwise we can use some of the famous sorting algorithms like selection sort, insertion sort, bubble sort, but all these algorithms can go to O(N*N) time complexity in the worst case.
    
3. What was the intuition behind this problem?
   Since we have to minimize the knapsacks we will try to include minimum weight with maximum weight so that at last we are able to minimize the total number of knapsacks and if we are not able to do so then we'll simply keep that max weight alone in a knapsack and will not be able to keep any other weight in the knapsack. For finding max and min weight we use the concept of sorting and two-pointer her.

Key Takeaways

In this blog, we solved the problem of minimizing the number of Knapsacks with total weight 'W' required to store Array containing elements greater than W/3.

Also Read - Selection Sort in C

If you want to learn more about two pointer approach, sorting, and arrays and want to practice some questions which require you to take your basic knowledge on these topics a bit higher, then you can visit our Guided Path for these topics individually on  Coding Ninjas Studio.To be more confident in data structures and algorithms, try out our DS and Algo Course. Till then, All the best for your future endeavors, and Keep Coding.