I recently encountered a problem that looks like a variation of bin packing or knapsack problem, but with the objective to maximise the number of bins/knapsacks:
Consider there is a list of M items with positive values v1 to vM respectively. There is also a standard size of bins which carries at most C items. The objective is to distribute items into as many bins as possible, with each bin having at least a total value of V. The problem is, given v1..vM, C and V, how to get the maximum possible number of filled bins? And the actual pattern?
My actual real life problem is actually one step more difficult. In addition to (A) filling in at most C items of a total value of at least V, there is another choice of (B) filling in at most C items of a total value of at least 2*V. Both kinds of bin can be produced for any number of times, but the second type of bin is (automatically) worth twice as the first type of bin. Then the problem is, what is the maximum possible worth of bins, i.e.
1 * number of type (A) bins + 2 * number of type (B) bins,
and the actual pattern?
I just made up the name "fukubukuro problem" for how I imagine its differences with knapsack problem :) I don't know the actual name of this problem yet, so I appreciate if anyone can give a direction on it. I also guess this can be solved by integer linear programming, but I hope to learn any more specific algorithms or approximations.