Pseudo-Polynomial Time Algorithms for Producing Cardinality Constrained Packages by Multi-Head Weighers

摘要

A subset selection problem from a finite set of items is considered, where a constraint is imposed on the cardinality of a selected subset. The subset selection problem is motivated by automated packaging systems, so-called multi-head weighers. Given a set of n items with their integral weights, a positive integer target weight t and a positive integer k, the subset selection problem asks to find a subset of the items so that the total weight of chosen items is no less than the target weight, and the number of the chosen items is exactly k, and further the total weight of them is as close to the target weight as possible. In this paper, an O(knt) time algorithm is presented to solve the subset selection problem. Numerical experiments are also conducted to demonstrate the performance of the pseudo-polynomial time algorithm on certain test instances having a feasible solution, and the results are reported.