En este desafío, se te pasan dos cosas:

1. Una longitud de cuerda, N
2. Una lista de cadenas, Lcada una con un valor de punto asignado. Cualquier cadena que no se pasa tiene un valor de punto de 0

Necesita construir una cadena de longitud Ntal que la suma de todos los puntos de la subcadena sea lo más grande posible.

Por ejemplo:

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

debería salir

ABCDG

Debido a que las dos subcadenas con puntos ( ABCy CDG) tienen un total de 5 puntos, y ninguna otra construcción posible puede dar 5 o más puntos.

Las subcadenas se pueden usar varias veces en una cadena y pueden superponerse. Puede suponer que los puntos siempre serán positivos, las longitudes de las subcadenas estarán entre 1 y los Ncaracteres, y eso N > 0. Si las construcciones múltiples son máximas, imprima cualquiera de ellas.

Su programa debe ejecutarse en un período de tiempo razonable (no más de un minuto para cada uno de los ejemplos):

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

Este es un código de golf , ¡así que prepara tu respuesta más corta en tu idioma favorito!

Python 2.7, 503 bytes

Esto no es particularmente golf, ni es particularmente eficiente; es solo una enumeración relativamente condensada de cadenas factibles forzadas por fuerza bruta. No creo que sea demasiado difícil crear una heurística admisible para usar con A *, lo que probablemente sería un poco más rápido. Sin embargo, no me molesté en hacer eso, porque este método resuelve todos los ejemplos en aproximadamente 47 segundos en mi computadora portátil.

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

Para probarlo:

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)

Explicación

La vfunción simplemente calcula el valor de una cadena dada buscando todas las ocurrencias de las subcadenas en L. La mfunción enumera todas las cadenas de longitud ncon prefijo eque se pueden generar a partir de las subcadenas en l. mrecursivamente se llama a sí mismo; la primera llamada debe pasar ''por e. Por ejemplo:

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

La pfunción simplemente recorre todas las cadenas posibles (como se enumera por m) y devuelve la que tiene el valor más alto (según lo determinado por v).

Tenga en cuenta que la mfunción realmente prioriza la enumeración ordenando según los valores de las subcadenas. Esto resulta innecesario para garantizar la optimización, y en realidad dificulta un poco la eficiencia; Podría ahorrar ~ 20 o más bytes eliminándolo.