In dieser Herausforderung haben Sie zwei Dinge bestanden:

1. Eine Stringlänge, N
2. Eine Liste von Zeichenfolgen mit Ljeweils einem zugewiesenen Punktwert. Jede Zeichenfolge, die nicht übergeben wird, hat den Punktwert 0

Sie müssen eine Zeichenfolge mit einer Nsolchen Länge erstellen, dass die Summe aller Teilzeichenfolgepunkte so groß wie möglich ist.

Beispielsweise:

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

sollte ausgeben

ABCDG

Weil die beiden Teilzeichenfolgen mit Punkten ( ABCund CDG) insgesamt 5 Punkte haben und keine andere mögliche Konstruktion 5 oder mehr Punkte ergeben kann.

Teilzeichenfolgen können in einer Zeichenfolge mehrfach verwendet werden und sich überlappen. Sie können davon ausgehen, dass die Punkte immer positiv sind, die Länge der Teilzeichenfolgen zwischen 1 und NZeichen beträgt und dass N > 0. Wenn mehrere Konstruktionen maximal sind, drucken Sie eine davon.

Ihr Programm muss in einer angemessenen Zeit ausgeführt werden (nicht mehr als eine Minute für jedes der Beispiele):

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

Dies ist ein Code-Golf , also bereiten Sie Ihre kürzeste Antwort in Ihrer Lieblingssprache vor!

Python 2.7, 503 Bytes

Dies ist nicht besonders gut und auch nicht besonders effizient. es ist nur eine relativ komprimierte Aufzählung möglicher Zeichenfolgen, die brachial erzwungen werden. Ich glaube nicht, dass es zu schwierig wäre, eine zulässige Heuristik für A * zu erstellen, was wahrscheinlich etwas schneller wäre. Das habe ich allerdings nicht gemacht, da mit dieser Methode alle Beispiele in ca. 47 Sekunden auf meinem Laptop gelöst werden.

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

Um es zu testen:

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)

Erläuterung

Die vFunktion berechnet einfach den Wert einer bestimmten Zeichenfolge, indem sie nach allen Vorkommen der Teilzeichenfolgen in L sucht. Die mFunktion zählt alle Zeichenfolgen nmit einem Präfix auf e, die aus den Teilzeichenfolgen in generiert werden können l. mruft sich rekursiv auf; Der erste Anruf sollte ''für übergeben werden e. Beispielsweise:

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

Die pFunktion durchläuft einfach alle möglichen Zeichenfolgen (wie von aufgezählt m) und gibt diejenige mit dem höchsten Wert (wie von bestimmt v) zurück.

Beachten Sie, dass die mFunktion die Aufzählung tatsächlich priorisiert, indem sie nach den Werten der Teilzeichenfolgen sortiert. Dies erweist sich als unnötig, um die Optimalität zu gewährleisten, und beeinträchtigt die Effizienz ein wenig. Ich könnte ~ 20 oder so Bytes sparen, indem ich es entferne.