Minimum number of elements required to make two bags of at least k weight?

Suppose you are given a number k and an array of objects having some weight. Now your task is to find the minimum number of objects that you can put in two bags such that each bag weigh at least k.
You can only take the objects as whole no breaking is allowed. Also, if an object is put in one bag it cannot be put into the other bag.

This problem seems simple to me. I have done similar problems when you need to fill just one bag. The idea I use is that you visit each object ask yourself what if I put it in the bag and what if I don’t? You do this recursively until your desired weight is reached or you have no more objects. Take minimum when calling your recursive function.

However, I am not able to understand how to keep track of all the objects used up in bag 1 so that I don’t include in bag 2.

Few Test cases

  1. Desired weight (k) = 4
    Number of objects (N) = 1
    [10]
    Output: -1 (Not possible)
  2. Desired weight (k) = 2
    Number of objects (N) = 3
    [2,2,2]
    Output: 2

Answer

Here is the sudo code for the program without dynamic programing.

 sort(a, a+n); // Sort the array of objects having weight
            int sum = a[n-1], count = -1; //Initialise sum and count
            unordered_set<int>log; // Create an unordered set to store logs (Unordered set will not add repetitive values in the log thus decreasing time complexity)
            log.insert(a[n-1]); // insert last element int log initially
            for(int i = n-2; i >=0; i--) {
                sum += a[i]; //increament the sum
                unordered_set<int>temp; //Create a temporary log that will be mapped to main log at the end.
                temp.insert(a[i]); //insert the sum to temp log
                for (auto it = log.begin(); it != log.end(); ++it) { //loop over all logs seen till now
                    temp.insert(*it + a[i]); // Add current sum to each of them and insert it to temp log thus creating all possible combinations.
                    if((a[i] + *it >= k) && (sum - a[i] - *it >= k)) { //Condition to check if bags have been filled with at least k weight.
                        count = n-i; // update the current count. This will be the ans.
                        break;
                    }
                    if(a[i] >= k && sum - a[i] >= k) {
                        count = n-i;
                        break;
                    }
                }
    
                if(count != -1) { //Condition to check if it's not possible to make such a combination.
                    break;
                }
                log.insert(temp.begin(), temp.end()); // add all temp to main log.
            }
            cout << count << endl; //print ans.

Leave a Reply

Your email address will not be published. Required fields are marked *