Conversione di un problema dello zaino limitato in un problema dello zaino 0/1

Potrebbe essere un errore nel tuo codice. Ho scritto il programma DP come menzionato da Naryshkin. Per l'intervallo di destinazione 13, riporta 6 + 7, e per 15, riporta 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)

Se si regola l'ordine delle lunghezze di input, può fornire altre soluzioni ottimali. Ad esempio, lens = 5*[3] + 6*[2] + 7*[1] + [10, 7, 6] darà 15 = 10 + 2 + 3.

Il modo in cui ho visto l'abitudine di trasformare un problema legato allo zaino in uno 0/1 è di avere più oggetti identici. Di 'se hai i seguenti oggetti (dati come peso, utilità):

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

Lo trasformeresti in un problema 0/1 utilizzando elementi con

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

E usa un algoritmo 0/1 per risolverlo. Probabilmente avrai più soluzioni di uguale correttezza, quindi ne selezioni una arbitraria.

Ora riguardo al problema del cavo: la lunghezza del cavo dovrebbe essere pari a quella del cavo e il valore di ciascun cavo è esattamente lo stesso (chiamalo 1, anche se qualsiasi valore positivo funzionerà). Ora, usa il tuo algoritmo di risoluzione di Knapsack preferito, ma dove normalmente sceglierai una soluzione (parziale) che massimizzi il valore, selezionane una che la minimizzi. Inoltre, ignorare tutte le soluzioni che non hanno un peso totale uguale alla capacità. Posso probabilmente (provare a) scrivere un algoritmo più concreto con codice effettivo se qualcuno lo vuole.