I want to make an application for generating a sequence (called S) of items (I), based on conditions (called C).

The Conditions are defined as a property with a 'bonus/reduction'. The total score (T) is defined by summing up al condition scores.

Some conditions are based on a specific item, some not.

Example (where Ix and Iy are different items) - Ix on first 5 places in S has a score of +20. - Ix directly after Iy has a score of -10.

However, I was wondering if there is an algorithm or principle for this problem (to find the highest total score)? It seems reasonably generic (except for the condition specification).

Finding the top score by trying all possibilities might end up in a lot of checks (like about 30! for 30 items).

Not all items have to be used in the sequence, but each item has a length, and there is a bonus for having the sum of length equal (as good as possible) to the requested length.

Each item can be used only once (at max).

  • $\begingroup$ Did I get it right that there is a fixed set of items, and the length of the sequence to generate is fixed and each item can be taken any number of times? $\endgroup$
    – kirelagin
    May 26 '15 at 12:30
  • $\begingroup$ Hm, your estimate of the running time of the trivial algorithm suggests, that the length is equal to the size of the set (multiset?) and each item in the set (multiset?) can be taken only once. $\endgroup$
    – kirelagin
    May 26 '15 at 12:32
  • $\begingroup$ The items are fixed, the length is not fixed (but each item has a time and the total time has to match approximately), any item can be taken only one time. $\endgroup$ May 26 '15 at 13:09

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.