We say that a multiset M dominates another multiset N if each element of N occurs at least as many times in M.
Given the target multiset M and the integer k> 0, I would like to find a list of L-networks of size-k whose sum is dominated by M. I would like this list to have a small cost, where my cost function has the form:
cost = c * m + n
where c is a constant, m is the number of multisets in L, and n is the number of different multisets in L.
How can i do this? An efficient algorithm to find the optimal solution would be ideal.
The problem is related to an attempt to fulfill a sales order to print pages with a specialized block printer that prints k pages at a time. Setting up a block printer to print a specific k-page template is expensive, but after initializing the template, printing with it is cheap. The target multiset M represents the sales order, and n different multisets of the list L represent n different k-page patterns.
In my particular application, M usually has> 30 elements whose multiplicities are in the range [10, 4, 10 ^ 6]. The value of k is 15, and c is approximately 10 ^ -5.
source share