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

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

<p>Some conditions are based on a specific item, some not.</p>

<p>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.</p>

<p>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).</p>

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

<p>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.</p>

<p>Each item can be used only once (at max).</p>

CC BY-SA 3.0
2015-05-26T12:30:18.083Z
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?
kirelagin
CC BY-SA 3.0
2015-05-26T12:32:13.347Z
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.
kirelagin
CC BY-SA 3.0
2015-05-26T13:09:18.157Z
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.
Michel Keijzers
<exp-time-algorithms>
Information about algorithm to generate sequences
Michel Keijzers
# Information about algorithm to generate sequences

(Asked by: username_0 on 2015-05-26)

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).

**Tags:** exp-time-algorithms
> **Comments:**
> **username_1**: 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?  
> **username_1**: 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.  
> **username_0**: 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.  

---

## 0 answers

