I have an algorithm problem which I do not know how to solve and I think it is NP-complete. Let me try to explain with a general example.
Given $n$ objects, each with $k$ possible properties, oversample (with replacement) among the $n$ objects to achieve a desired proportion of objects with specific properties and sample each of the $n$ objects at least once. Note that each object can have several properties. Therefore, if you sample an object with multiple properties, multiple proportions will be affected (and of course all proportions will be affected).
Specific example: a bag contains 6 objects, each with 3 possible properties: color (e.g. blue), shape (e.g. Cube), and temperature (e.g. cold).
- Object 1: Blue
- Object 2: Blue
- Object 3: Blue, Cube
- Object 4: Blue
- Object 5: Blue, Cold
- Object 6: Blue, Cube, Cold
The current proportions are: 100 % blue, 33 % cube, 33 % cold.
The goal is to specify a desired proportion, like: 100 % blue, 50 % cube and 33 % cold. To achieve this I can sample Object 3 and Object 6 to get 100 % blue, 50 % cube and 37.5 % cold or sample Object 3 twice to get 100 % blue, 50 % cube and 25 % cold. Both solutions are accepted, I just want an approximate.
Is there an algorithm or approximation algorithm to do this?