Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
1.
Problem statement
2.
Approach
3.
Algorithm
4.
Code:
5.
Time Complexity
6.
Space Complexity
7.
8.
Key Takeaways
Last Updated: Mar 27, 2024

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

Apoorv
1 upvote

## Problem statement

In this problem, we are given a weight 'W,' and an array consisting of some weights, and the value of all the weights in the Array is more than 'W/3' the final goal is to minimize the total number of knapsacks required to store the elements of the Array.

Example 1

Input:

Let the input array be like weights = [ 80,120,100,150 ] and W = 200

Output:

3

Explanation:

[150], [80,100], [120], These 3 Knapsacks will be used to store the entire Array of weights.

As for the first knapsack total weight is 150 <= 200

For the second knapsack total weight is 180 <= 200

For the third knapsack total weight is 120 <= 200

Example 2

Input:

Let the input array be like weights = [ 150,180, 200,150]  and W = 400

Output:

2

Explanation:

[150,200],[150,180], These 2 Knapsacks will be used to store the entire Array of weights

## Approach

To minimize the number of Knapsacks to store the entire Array, we can use the concept of two pointers. We can sort the Array and can iterate through the Array from both the ends and try to include value with maximum value and value with minimum weight in a single knapsack. This will solve the problem for us in a greedy approach.

## 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:

## 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.

Live masterclass