Bin-packing: Maximise number of bins / “Fukubukuro” problem?

Question

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 v₁ to v_M 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 v₁..v_M, 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.

Answer 1

I found a paper (circa 2005) by Boyar et al which studies algorithms for problems of this type, which they call maximum resource bin-packing problems (to contrast with the usual goal of bin-packing to minimize a resource such as the number of bins).

Usually, for bin packing problems, we try to minimize the number of bins used or in the case of the dual bin packing problem, maximize the number or total size of accepted items. This paper presents results for the opposite problems, where we would like to maximize the number of bins used or minimize the number or total size of accepted items. We consider off-line and on-line variants of the problems.

By on-line variants are meant problems in which a "current item" must be assigned to a bin before proceeding to the next item, while off-line variants permit selection of items for assignment without regard to such input sequencing.

Performance of an algorithm is assessed by bounding the optimal solution OPT(I) (maximum number of bins used) with a linear function $c$ ALG(I) + $b$ of the number used by the algorithm, and defining approximation ratio $\mathcal{R}_{ALG}$ to be the infimum of $c$ over all inputs I.

The authors note a similarity between the Bin-Covering Problem where bin capacity is 1 and Maximum Resource Bin-Packing with twice the bin capacity (2). In Bin-Covering the goal is assigning items to meet or exceed the capacity of as many bins as possible.

Answer 2

Actually, this problem dates back to 1978, check out the paper

• E. G. Coffman, J. Y.-T. Leung, and D. W. Ting, "Bin packing: Maximizing the number of pieces packed," Acta Informatica, vol. 9, no. 3, pp. 263–271, Sep. 1978.