Przekształcanie problemu związanego z plecakiem w problem plecaka 0/1

Natknąłem się na problem, w którym celem było zastosowanie programowania dynamicznego (zamiast innych podejść). Należy rozstawić odległość i zestaw kabli o różnych długościach. Jaka jest minimalna liczba kabli potrzebnych do dokładnego rozłożenia odległości?

Dla mnie wyglądało to na problem z plecakiem , ale ponieważ mogły istnieć wielokrotności określonej długości, był to problem związany z plecakiem, a nie problem z plecakiem 0/1. (Traktuj wartość każdego przedmiotu jako jego wagę.) Biorąc naiwne podejście (i nie troszcząc się o rozszerzenie przestrzeni poszukiwań), metoda, którą zastosowałem, aby przekształcić problem związany z plecakiem w problem plecaka 0/1, była po prostu podziel wielokrotności na pojedyncze i zastosuj dobrze znany algorytm programowania dynamicznego. Niestety prowadzi to do nieoptymalnych wyników.

Na przykład podane kable:
1 x 10 stóp,
1 x 7 stóp,
1 x 6 stóp,
5 x 3 stopy ,
6 x
2 stopy , 7 x 1 stóp

Jeśli rozpiętość docelowa wynosi 13 stóp, algorytm DP wybiera 7 + 6 w celu ustalenia odległości. Chciwy algorytm wybrałby 10 + 3, ale jest to remis dla minimalnej liczby kabli. Problem pojawia się przy próbie rozciągnięcia na 15 stóp. Algorytm DP ostatecznie wybrał 6 + 3 + 3 + 3, aby uzyskać 4 kable, podczas gdy chciwy algorytm poprawnie wybiera 10 + 3 + 2 tylko dla 3 kabli.

W każdym razie, dokonując lekkiego skanowania konwersji ograniczonej do 0/1, wydaje się, że jest to dobrze znane podejście do konwersji wielu elementów na {p, 2p, 4p ...}. Moje pytanie brzmi, jak działa ta konwersja, jeśli p + 2p + 4p nie sumuje się do liczby wielu elementów. Na przykład: Mam 5 kabli o długości 3 stóp. Nie mogę bardzo dobrze dodać {3, 2x3, 4x3}, ponieważ 3 + 2x3 + 4x3> 5x3. Czy zamiast tego powinienem dodać {3, 4x3}?

[Obecnie próbuję przejrzeć artykuł „Oregon Trail Knapsack Problem”, ale obecnie wygląda na to, że zastosowane podejście nie polega na programowaniu dynamicznym.]

Może to być jakiś błąd w twoim kodzie. Napisałem program DP, jak wspomniał Naryshkin. Dla zakresu docelowego 13 zgłasza 6 + 7, a dla 15 zgłasza 2 + 6 + 7.

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

Jeśli zmienisz kolejność długości wejściowych, może dać inne optymalne rozwiązania. Na przykład lens = 5*[3] + 6*[2] + 7*[1] + [10, 7, 6]da 15 = 10 + 2 + 3.

Sposób, w jaki widziałem, jak przekształcić problem związany z plecakiem w 0/1, to po prostu posiadanie wielu identycznych przedmiotów. Powiedz, czy masz następujące elementy (podane jako waga, użyteczność):

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

Przekształciłbyś go w problem 0/1 używając przedmiotów z

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

I użyj algorytmu 0/1, aby go rozwiązać. Prawdopodobnie będziesz mieć wiele rozwiązań o jednakowej poprawności, więc wybierzesz dowolne.

Teraz o twoim problemie z przewodem: chciałbym, aby długość kabla była wagą, a wartość każdego kabla była dokładnie taka sama (nazwij to 1, chociaż jakakolwiek wartość dodatnia będzie działać). Teraz użyj swojego ulubionego algorytmu rozwiązywania plecaków, ale tam gdzie normalnie wybierzesz (częściowe) rozwiązanie, które maksymalizuje wartość, wybierz takie, które ją minimalizuje. Pomiń także wszystkie rozwiązania, które nie mają całkowitej masy równej pojemności. Prawdopodobnie mogę (próbować) napisać bardziej konkretny algorytm z rzeczywistym kodem, jeśli ktoś tego chce.