c++ - 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

question from:https://stackoverflow.com/questions/65643970/minimum-number-of-elements-required-to-make-two-bags-of-at-least-k-weight

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