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

Question

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 1

I will focus on what you point out as your actual core problem, how to keep track of objects you used in one bag, the other bag or not at all.

Make a list (array, vector, ... whatever container you prefer) and note for each of the objects where you used it - or not.

index	value	meaning
0	0	not used
1	0	not used
2	0	not used
3	1	used in one bag
4	2	used in other bag

From your question it is not clear to me whether all objects have the same weight or different weights given in the input. If the weights are different, then you most likely already have a container for keeping track of the weight of each object. Modifying that container or using a second, very similar one will help you to also store the "used where" information.

I am intentionally not going into detail, because of
How do I ask and answer homework questions?

Answer 2

I don't know if this answers your question or not, but still... You can do one thing: Initially make two empty arrays, say Bag_1 and Bag_2. As you recurse through all elements one by one, pop that element out of the array and append it to Bag_1 or Bag_2 whichever gives you the optimal solution. If the process is to be done multiple times, then creating a copy of the original array might help, if the length of the array is reasonable.

Answer 3

Here is the pseudo 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]; //increment 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.