I have three types of items: $a_1$, $a_2$ and $a_3$, each with quantities $c_1$, $c_2$, and $c_3$. I can combine one of each of two different types of items (for example combining $a_1$ with $a_3$) into a product $p_{ij}$ which has a value of $v_{ij}$. The value of each product is not related to the individual items, but specifically to the combination of those items. With 3 types of items, there are only 3 possible products, but the number of products increase when given a generalized number of item types $a_n$.

How do I maximize the total value all items paired into products, given limited and differing quantities for each item?

I have been struggling for a way of formally conceptualizing this problem in order to find an algorithm that may work. I've spent time learning about knapsack and generalized assignment problems to see if I can fit this problem into one of those to no avail. A greedy algorithm will, of course, find a local max, and I will probably end up using that if I can't figure out anything better.


closed as unclear what you're asking by Namaste, Daniel W. Farlow, José Carlos Santos, Claude Leibovici, user91500 Jul 26 '17 at 9:00

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Have you had a look at linear programming? $\endgroup$ – Jens Jul 25 '17 at 23:08
  • $\begingroup$ I had not. I think that's what I'm looking for: Maximize:$$v_{12}p_{12}+v_{13}p_{13}+v_{23}p_{23}$$Subject to:$$a_{11}p_{12}+a_{12}p_{13} \le a_1$$$$a_{21}p_{12}+a_{22}p_{23}\le a_2$$$$a_{31}p_{13}+a_{32}p_{23} \le a_3$$ $\endgroup$ – Rek Jul 26 '17 at 0:54
  • $\begingroup$ Glad to help! If you need additional guidance, I suggest asking a new question outlining the problem, where you include the tag "linear-programming". I'm not an expert on the topic, but others are. $\endgroup$ – Jens Jul 26 '17 at 1:14
  • $\begingroup$ Will do, thanks. $\endgroup$ – Rek Jul 26 '17 at 1:27

Browse other questions tagged or ask your own question.