'Maximize value from pool of items

I have a pool of items, consisting of a finite set of types (A, B, ..., J) with finite quantities (a, b, ..., j). Each type of item has their own cost and value associated with them, where strictly:

  • A.cost ≤ B.cost ≤ ... ≤ J.cost
  • A.value ≤ B.value ≤ ... ≤ J.value
  • A.value/A.cost ≥ B.value/B.cost ≥ ... ≥ J.value/J.cost

I want to maximize the total value, with the following constraints:

  1. Maximum number of items must be less than or equal to an inputted total limit
  2. Sum of costs must be less than or equal to an inputted total cost

My current solution for all intents and purposes arranges the pool in an ordered list (in decreasing relative value) and selects a sub-list, satisfying primarily constraint #1 then constrain #2

As an example:

[A,A,A,A, B,B, C,C, D, F,F, G, ...] may result in something like: [A,B,B,C], if the total limit was 4 and [B,B,C,C] would have exceeded the total cost. This simple solution works well in the majority of cases, however in practical applications I've found that I could find a better total value by substituting one or more items for the next more costly item if I had too large a remainder for constraint #2.

Rather than extending my existing solution, which I believe has some major limitations, how would I go about solving this mathematically; with the limitation being that it's going to be implemented in low level language(s) and time sensitive, making complex matrix computations potentially nonviable.



Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source