Convertendo um problema de mochila limitado para 0/1

Encontrei um problema em que o objetivo era usar a programação dinâmica (em vez de outras abordagens). Há uma distância a ser estendida e um conjunto de cabos de diferentes comprimentos. Qual é o número mínimo de cabos necessários para percorrer exatamente a distância?

Para mim, isso parecia um problema de mochila , mas como poderia haver múltiplos de um comprimento específico, era um problema de mochila limitado, em vez de um problema de mochila 0/1. (Trate o valor de cada item como seu peso.) Adotando a abordagem ingênua (e não se importando com a expansão do espaço de pesquisa), o método que eu usei para converter o problema da mochila limitada em um problema da mochila 0/1 era simplesmente divida os múltiplos em singles e aplique o conhecido algoritmo de programação dinâmica. Infelizmente, isso leva a resultados abaixo do ideal.

Por exemplo, cabos fornecidos:
1 x 10 pés,
1 x
7 pés, 1 x 6 pés,
5 x 3 pés,
6 x 2 pés,
7 x 1 pé

Se o intervalo alvo for de 13 pés, o algoritmo DP seleciona 7 + 6 para expandir a distância. Um algoritmo ganancioso teria escolhido 10 + 3, mas é um empate para o número mínimo de cabos. O problema surge ao tentar abranger 15 pés. O algoritmo DP acabou escolhendo 6 + 3 + 3 + 3 para obter 4 cabos, enquanto o algoritmo ganancioso escolhe corretamente 10 + 3 + 2 para apenas 3 cabos.

De qualquer forma, ao fazer uma varredura leve de conversão limitada a 0/1, parece a abordagem conhecida para converter vários itens em {p, 2p, 4p ...}. Minha pergunta é como essa conversão funciona se p + 2p + 4p não soma o número de vários itens. Por exemplo: eu tenho 5 cabos de 3 pés. Não posso muito bem adicionar {3, 2x3, 4x3} porque 3 + 2x3 + 4x3> 5x3. Devo adicionar {3, 4x3}?

[Atualmente, estou tentando escrever o artigo "Oregon Trail Knapsack Problem", mas atualmente parece que a abordagem usada não é a programação dinâmica.]

Pode haver algum erro no seu código. Eu escrevi o programa de DP, como mencionado por Naryshkin. Para o intervalo de destino 13, ele reporta 6 + 7 e, para 15, ele reporta 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 você ajustar a ordem dos comprimentos de entrada, poderá fornecer outras soluções ideais. Por exemplo, lens = 5*[3] + 6*[2] + 7*[1] + [10, 7, 6]dará 15 = 10 + 2 + 3.

A maneira que eu vi usada para transformar um problema de mochila limitada em um 0/1 é ter apenas vários itens idênticos. Diga se você possui os seguintes itens (dados como peso, utilidade):

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

Você o transformaria em um problema 0/1 usando itens com

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

E use um algoritmo 0/1 para resolvê-lo. Você provavelmente terá várias soluções com a mesma exatidão para selecionar uma arbitrária.

Agora, sobre o seu problema de fio: gostaria que o comprimento do cabo fosse o peso e o valor de cada cabo fosse exatamente o mesmo (chame-o de 1, embora qualquer valor positivo funcione). Agora, use seu algoritmo favorito de solução de mochila, mas onde você normalmente selecionaria uma solução (parcial) que maximiza o valor, selecione uma que a minimize. Além disso, desconsidere todas as soluções que não possuem um peso total igual à capacidade. Provavelmente, posso (tentar) escrever um algoritmo mais concreto com código real, se alguém quiser.