Suppose we have 2 lists:

List $G$: the goal, contains goal items each comes with a specific amount, $$G = \{i_1 \times Item_1, i_2 \times Item_2,\dots, i_n \times Item_n\}$$

List $I$: a list that contains lists of items each also comes with a specific amount, $$I = \{\{j_1 \times Item_1, j_3 \times Item_3\}, \{k_2 \times Item_2, k_3 \times Item_3,k_5 \times Item_5\}, \dots\}$$

Each of the lists in $I$ costs some amount to pick out and we know them.
It is guaranteed that each item in $G$ will appear in $I$ at least once.

Find a way to pick lists from $I$ so that their total items will be equal or exceed that of $G$ but also minimize the cost.
You can pick as many lists as you want and duplicates are allowed.

This problem came up to me while planning to make a tool for a game.

  • 1
    $\begingroup$ It's a multiset version of Weighted Set Cover. It's definitely NP-hard, since if there was an efficient algorithm for it, you could use it to solve any Set Cover problem, just by setting all $i_{i'}$ and $j_{j'}$ values to 1. $\endgroup$ – j_random_hacker May 10 '19 at 20:32
  • 2
    $\begingroup$ The most practical approach is likely to be formulating it as an ILP: there are good existing solvers, and this has the side benefit of giving you a lower bound by relaxing the integrality constraint. $\endgroup$ – j_random_hacker May 10 '19 at 20:35
  • $\begingroup$ Please edit the question to add a reference to the original problem. $\endgroup$ – John L. May 10 '19 at 20:37
  • $\begingroup$ @Apass.Jack i can't find any reference yet for my problem. The problem came up to me while planning to make a tool for a game. $\endgroup$ – Koozing May 11 '19 at 4:05
  • $\begingroup$ @Koozing, I just edited the question to include that piece of information. It is always important and helpful to explain the motivation of your post unless it is obvious such as when it comes from a standard course on computer science. $\endgroup$ – John L. May 11 '19 at 4:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.