Konvertieren eines begrenzten Rucksackproblems in ein 0/1-Rucksackproblem

Ich bin auf ein Problem gestoßen, bei dem es das Ziel war, dynamische Programmierung zu verwenden (anstelle von anderen Ansätzen). Es gibt eine zu überbrückende Distanz und eine Reihe von Kabeln unterschiedlicher Länge. Wie viele Kabel sind mindestens erforderlich, um die Entfernung genau zu überbrücken?

Für mich sah das nach einem Rucksackproblem aus , aber da es ein Vielfaches einer bestimmten Länge geben konnte, war es eher ein begrenztes Rucksackproblem als ein 0/1-Rucksackproblem. (Betrachten Sie den Wert jedes Artikels als sein Gewicht.) Die Methode, mit der ich das begrenzte Rucksackproblem in ein 0/1-Rucksackproblem umgewandelt habe, war ganz einfach Teilen Sie die Multiples in Singles auf und wenden Sie den bekannten dynamischen Programmieralgorithmus an. Dies führt leider zu suboptimalen Ergebnissen.

Zum Beispiel gegebene Kabel:
1 x 10 Fuß,
1 x 7 Fuß, 1 x 6
Fuß,
5 x 3 Fuß,
6 x 2 Fuß,
7 x 1 Fuß

Wenn die Zielspanne 13 Fuß beträgt, wählt der DP-Algorithmus 7 + 6, um die Entfernung zu überspannen. Ein gieriger Algorithmus hätte 10 + 3 gewählt, aber es ist ein Gleichstand für die minimale Anzahl von Kabeln. Das Problem entsteht, wenn versucht wird, 15ft zu überspannen. Der DP-Algorithmus hat 6 + 3 + 3 + 3 ausgewählt, um 4 Kabel zu erhalten, während der Greedy-Algorithmus 10 + 3 + 2 für nur 3 Kabel korrekt auswählt.

Auf jeden Fall scheint es, als wäre es ein bekannter Ansatz, mehrere Elemente in {p, 2p, 4p ...} umzuwandeln, wenn man eine leichte Abtastung der auf 0/1 beschränkten Konvertierung vornimmt. Meine Frage ist, wie diese Konvertierung funktioniert, wenn p + 2p + 4p nicht die Anzahl mehrerer Elemente ergibt. Zum Beispiel: Ich habe 5 3ft Kabel. Ich kann {3, 2x3, 4x3} nicht gut addieren, da 3 + 2x3 + 4x3> 5x3. Soll ich stattdessen {3, 4x3} hinzufügen?

[Ich versuche derzeit, das "Oregon Trail Knapsack Problem" -Papier zu untersuchen, aber es sieht derzeit so aus, als ob es sich bei dem dort verwendeten Ansatz nicht um dynamische Programmierung handelt.]

Es könnte ein Fehler in Ihrem Code sein. Ich habe das von Naryshkin erwähnte DP-Programm geschrieben. Für die Zielspanne 13 werden 6 + 7 und für 15 2 + 6 + 7 gemeldet.

# weight: cable length
# total weight: target span
# value: 1 for each cable
# want minimum number of cables, i.e. minimum total value

def knapsack_01_exact_min(weights, values, W):
    # 0-1 knapsack, exact total weight W, minimizing total value
    n = len(weights)
    values = [0] + values
    weights = [0] + weights
    K = [[0 for i in range(W+1)] for j in range(n+1)]
    choice = [[0 for i in range(W+1)] for j in range(n+1)]
    for i in range(1, n+1):
        for w in range(1, W+1):
            K[i][w] = K[i-1][w]
            choice[i][w] = '|'
            if w >= weights[i]:
                t = K[i-1][w-weights[i]]
                if (w==weights[i] or t) and (K[i][w]==0 or t+values[i] < K[i][w]):
                    choice[i][w] = '\\'
                    K[i][w] = t+values[i]
    return K[n][W], choice

def print_choice(choice, weights):
    i = len(choice)-1
    j = len(choice[0])-1
    weights = [0] + weights
    while i > 0 and j > 0:
        if choice[i][j]=='\\':
            print weights[i],
            j -= weights[i]
        i -= 1
    print

lens = [10, 7, 6] + 5*[3] + 6*[2] + 7*[1]
values = (3+5+6+7)*[1]
span = 13
v, choice = knapsack_01_exact_min(lens, values, span)
print "need %d cables to span %d:" % (v,span),
print_choice(choice, lens)

span = 15
v, choice = knapsack_01_exact_min(lens, values, span)
print "need %d cables to span %d:" % (v,span),
print_choice(choice, lens)

Wenn Sie die Reihenfolge der Eingabelängen anpassen, können Sie andere optimale Lösungen finden. Zum Beispiel lens = 5*[3] + 6*[2] + 7*[1] + [10, 7, 6]ergibt 15 = 10 + 2 + 3.

Die Art und Weise, wie ich es gesehen habe, um ein eingeschränktes Rucksackproblem in ein 0/1-Problem umzuwandeln, besteht darin, einfach mehrere identische Elemente zu haben. Sagen Sie, wenn Sie die folgenden Gegenstände haben (angegeben als Gewicht, Nutzen):

• 2 x 1, 2
• 3 x 2, 3

Sie würden es in ein 0/1-Problem umwandeln, indem Sie Elemente mit verwenden

• 1, 2
• 1, 2
• 2, 3
• 2, 3
• 2, 3

Und verwenden Sie einen 0/1-Algorithmus, um es zu lösen. Sie werden wahrscheinlich mehrere Lösungen mit gleicher Korrektheit haben, also wählen Sie eine beliebige aus.

Nun zu Ihrem Drahtproblem: Ich hätte die Länge des Kabels als das Gewicht und den Wert jedes Kabels genau gleich (nennen Sie es 1, obwohl jeder positive Wert funktionieren wird). Verwenden Sie nun Ihren bevorzugten Knapsack-Lösungsalgorithmus. Wenn Sie jedoch normalerweise eine (Teil-) Lösung auswählen, die den Wert maximiert, wählen Sie eine Lösung aus, die ihn minimiert. Ignorieren Sie auch alle Lösungen, deren Gesamtgewicht nicht der Kapazität entspricht. Ich kann wahrscheinlich (versuchen) einen konkreteren Algorithmus mit tatsächlichem Code schreiben, wenn es jemand will.