Dans ce défi, vous passez deux choses:

1. Une longueur de chaîne, N
2. Une liste de chaînes, Lchacune avec une valeur de point assignée. Toute chaîne non transmise a une valeur en points de 0

Vous devez construire une chaîne de longueur Ntelle que la somme de tous les points de sous-chaîne soit aussi grande que possible.

Par exemple:

5 [("ABC", 3), ("DEF", 4), ("CDG", 2)]

devrait sortir

ABCDG

Parce que les deux sous-chaînes avec des points ( ABCet CDG) ont un total de 5 points, et aucune autre construction possible ne peut donner 5 points ou plus.

Les sous-chaînes peuvent être utilisées plusieurs fois dans une chaîne et peuvent se chevaucher. Vous pouvez supposer que les points seront toujours positifs, la longueur des sous-chaînes sera comprise entre 1 et les Ncaractères longs, et cela N > 0. Si plusieurs constructions sont maximales, imprimez l'une d'entre elles.

Votre programme doit s'exécuter dans un délai raisonnable (pas plus d'une minute pour chacun des exemples):

1 [("A", 7), ("B", 4), ("C", 100)]     => C
2 [("A", 2), ("B", 3), ("AB", 2)]      => AB
2 [("A", 1), ("B", 2), ("CD", 3)]      => BB
2 [("AD", 1), ("B", 2), ("ZB", 3)]     => ZB
3 [("AB", 2), ("BC", 1), ("CA", 3)]    => CAB
3 [("ABC", 4), ("DEF", 4), ("E", 1)]   => DEF
4 [("A", 1), ("BAB", 2), ("ABCD", 3)]  => AAAA or ABAB or BABA or ABCD
5 [("A", 1), ("BAB", 2), ("ABCD", 3)]  => BABCD or BABAB
5 [("ABC", 3), ("DEF", 4), ("CDG", 2)] => ABCDG
5 [("AB", 10), ("BC", 2), ("CA", 2)]   => ABCAB
6 [("AB", 10), ("BC", 2), ("CA", 2)]   => ABABAB
8 [("AA", 3), ("BA", 5)]               => BAAAAAAA
10 [("ABCDE", 19), ("ACEBD",  18), ("ABEDC", 17), ("BCEDA", 16), ("EBDAC", 15), ("BACD", 14), ("CADB", 13), ("ABDC", 12), ("CABD", 11), ("EBDC", 10), ("ACE", 9), ("CBA", 8), ("AEC", 7), ("BE", 6), ("AE", 5), ("DC", 4), ("BA", 3), ("A", 2), ("D", 1)]
=> ACEBDACEBD

Ceci est un code-golf , alors préparez votre réponse la plus courte dans votre langue préférée!

Python 2.7, 503 octets

Ce n'est pas particulièrement golfé, ni particulièrement efficace; c'est juste une énumération relativement condensée de chaînes possibles qui sont forcées par la force brute. Je ne pense pas qu'il serait trop difficile de créer une heuristique admissible à utiliser avec A *, ce qui serait probablement un peu plus rapide. Je n'ai pas pris la peine de le faire, car cette méthode résout tous les exemples en 47 secondes environ sur mon ordinateur portable.

import re
v=lambda l,s:sum([len([m.start() for m in re.finditer('(?=%s)'%u,s)])*v for u,v in l])
def m(n,l,e):
 if len(e)==n:
  yield e
 else:
  u=1
  for s,v in sorted(l,key=lambda j:j[1],reverse=True):
   for i in range(len(s)-1,0,-1):
    if len(e)+len(s)-i <= n and e.endswith(s[:i]):
     for r in m(n,l,e+s[i:]):
      u=0;yield r
   if len(e)+len(s)<=n:
    for r in m(n,l,e+s):
     u=0;yield r
  if u:
   yield e
def p(n,l):
 b,r=-1,0
 for s in m(n,l,''):
  a=v(l,s)
  if a>b:b,r=a,s
 return r

Pour le tester:

if __name__ == "__main__":
    for n, l in [
            (1, [("A", 7), ("B", 4), ("C", 100)]),     # => C
            (2, [("A", 2), ("B", 3), ("AB", 2)]),      # => AB
            (2, [("A", 1), ("B", 2), ("CD", 3)]),      # => BB
            (2, [("AD", 1), ("B", 2), ("ZB", 3)]),     # => ZB
            (3, [("AB", 2), ("BC", 1), ("CA", 3)]),    # => CAB
            (3, [("ABC", 4), ("DEF", 4), ("E", 1)]),   # => DEF
            (4, [("A", 1), ("BAB", 2), ("ABCD", 3)]),  # => AAAA or ABAB or BABA or ABCD
            (5, [("A", 1), ("BAB", 2), ("ABCD", 3)]),  # => BABCD or BABAB
            (5, [("ABC", 3), ("DEF", 4), ("CDG", 2)]), # => ABCDG
            (5, [("AB", 10), ("BC", 2), ("CA", 2)]),   # => ABCAB
            (6, [("AB", 10), ("BC", 2), ("CA", 2)]),   # => ABABAB
            (8, [("AA", 3), ("BA", 5)]),               # => BAAAAAAA
            (10, [("ABCDE", 19), ("ACEBD",  18), ("ABEDC", 17), ("BCEDA", 16), ("EBDAC", 15), ("BACD", 14), ("CADB", 13), ("ABDC", 12), ("CABD", 11), ("EBDC", 10), ("ACE", 9), ("CBA", 8), ("AEC", 7), ("BE", 6), ("AE", 5), ("DC", 4), ("BA", 3), ("A", 2), ("D", 1)]) # => ACEBDACEBD
    ]:
        print p(n, l)

Explication

La vfonction calcule simplement la valeur d'une chaîne donnée en recherchant toutes les occurrences des sous-chaînes dans L. La mfonction énumère toutes les chaînes de longueur navec préfixe equi peuvent être générées à partir des sous-chaînes dans l. ms'appelle récursivement; devrait passer dans le premier appel ''pour e. Par exemple:

>>> for s in m(4, [("A", 1), ("BAB", 2), ("ABCD", 3)], ''):print s
ABCD
BABA
ABCD
ABAB
AAAA

La pfonction parcourt simplement toutes les chaînes possibles (comme énuméré par m) et renvoie celle avec la valeur la plus élevée (déterminée par v).

Notez que la mfonction priorise réellement l'énumération en triant en fonction des valeurs des sous-chaînes. Cela s'avère inutile pour garantir l'optimalité, et cela nuit en fait un peu à l'efficacité; Je pourrais économiser environ 20 octets en le supprimant.