Fractional Knapsack

Q: Qual é a complexidade de tempo do problema da mochila fracionária?

Ordenar os itens por valor por peso custa O(n log n) e o preenchimento é feito em uma única passagem, então o total é O(n log n) , com espaço O(n) para a ordenação. Procurar o item mais denso a cada rodada custa O(n²) .

Q: Como resolver o problema da mochila fracionária sem números de ponto flutuante?

Com pesos positivos, a / b > c / d é o mesmo teste que a × d > c × b , então compare as densidades multiplicando em cruz. O melhor valor é um número inteiro mais uma fração, values[i] × room / weights[i] para o item fracionado, então uma divisão inteira fornece exatamente a resposta arredondada para baixo.

MédioGuloso Ordenação

+10

Você tem n itens. O item i vale values[i] e pesa weights[i]. Sua mochila comporta um peso total de, no máximo, capacity, e você pode pegar qualquer parte de um item: um pedaço do item i que pesa w vale values[i] × w / weights[i].

Escreva uma função chamada fractionalKnapsack que retorne o maior valor total que a mochila pode carregar, arredondado para baixo até um número inteiro.

Função

fractionalKnapsack(values: integer-array, weights: integer-array, capacity: integer) → integer

valuesinteger-array: o valor de cada item
weightsinteger-array: o peso de cada item
capacityinteger: o maior peso que a mochila pode suportar
Retornainteger: o maior valor total que cabe na mochila, arredondado para baixo

Restrições

1 ≤ n ≤ 5000, onde n = values.length = weights.length
1 ≤ values[i], weights[i] ≤ 10⁴
1 ≤ capacity ≤ 10⁸

Exemplos

Entrada: values = [40, 90, 30, 50]weights = [8, 30, 5, 20]capacity = 40
Saída: 151
Explicação: Por unidade de peso, os itens valem 5, 3, 6 e 2.5. Os itens 2 e 0 entram inteiros, somando 70, e restam 27 de capacidade; 27 das 30 unidades do item 1 acrescentam 81, totalizando 151.

Entrada: values = [10, 7]weights = [4, 3]capacity = 5
Saída: 12
Explicação: O item 0 vale 2.5 por unidade e o item 1, cerca de 2.33, então o item 0 entra inteiro por 10. Uma das 3 unidades do item 1 acrescenta 7 / 3, e 12 e um terço é arredondado para baixo, resultando em 12.

Para ir além

Você consegue encontrar a resposta em tempo O(n), sem ordenar todos os itens?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Como você pode fracionar os itens, o problema é guloso, ao contrário da mochila 0/1: cada unidade de peso deve vir do item que ainda tem o maior valor por unidade. Ordene por essa densidade e encha a mochila nessa ordem. Compare as densidades multiplicando em cruz e arredonde para baixo apenas o item que você fracionar, para que nenhuma fração seja armazenada.

Escolha o item mais denso a cada rodada

Correta, mas não termina nos maiores testes

Intuição

Encha a mochila começando pelo item de maior densidade: pegue-o inteiro se couber; caso contrário, pegue a parte que enche a mochila e pare. Encontre o item não utilizado de maior densidade percorrendo todos eles e comparando values[i] × weights[j] com values[j] × weights[i], em vez de dividir. Com pesos positivos, é o mesmo teste, e ambos os produtos ficam abaixo ou iguais a 10^8.

Escolher primeiro o item de maior densidade é melhor: se uma carga contém algum peso de um item menos denso enquanto um item mais denso ainda não foi totalmente incluído, trocar esse peso pelo item mais denso não pode diminuir o valor. Continue fazendo trocas e você chegará à carga com os itens em ordem decrescente de densidade.

Até n rodadas percorrem os itens não utilizados, resultando em cerca de n²/2 = 12.5 milhões de comparações para n = 5000.

Algoritmo

Marque todos os itens como não utilizados e defina room = capacity e total = 0.
Enquanto houver espaço, examine os itens não utilizados em busca do mais denso, comparando as densidades por multiplicação cruzada.
Se não restar nenhum item, pare. Caso contrário, marque esse item como utilizado.
Se ele couber, adicione seu valor a total e subtraia seu peso de room. Se não couber, adicione values[i] × room / weights[i] com divisão inteira e pare.
Retorne total.

def fractionalKnapsack(values, weights, capacity):
    n = len(values)
    used = [False] * n
    total = 0
    room = capacity
    while room > 0:
        best = -1
        for i in range(n):
            # i is denser than best: values[i] / weights[i] > values[best] / weights[best], cross-multiplied
            if not used[i] and (best == -1 or values[i] * weights[best] > values[best] * weights[i]):
                best = i
        if best == -1:
            break  # every item is already in the bag
        used[best] = True
        if weights[best] <= room:
            total += values[best]
            room -= weights[best]
        else:
            total += values[best] * room // weights[best]  # the part that fits, rounded down
            room = 0
    return total

Ordenar por valor por peso

Intuição

A varredura encontra o item de maior densidade repetidamente, mas a ordem nunca muda entre as rodadas. Ordene os itens uma vez, do mais denso para o menos denso, usando a mesma comparação com multiplicação cruzada. Itens com a mesma densidade podem ficar em qualquer ordem, pois têm o mesmo valor por unidade.

Adicione os itens inteiros enquanto couberem. O primeiro que não couber é o único que você divide: ele acrescenta values[i] × room / weights[i], e a divisão inteira arredonda esse valor para baixo. Tudo antes dele é um número inteiro, então arredondar esse único termo dá a resposta exata. A ordenação custa O(n log n) e a percorrida custa O(n).

Algoritmo

Crie uma lista dos índices dos itens e ordene-a do mais denso para o menos denso usando a comparação com multiplicação cruzada.
Defina room = capacity e total = 0.
Para cada item nessa ordem, se weights[i] ≤ room, some seu valor e subtraia seu peso de room.
Caso contrário, some values[i] × room / weights[i] usando divisão inteira e pare.
Retorne total.

from functools import cmp_to_key


def fractionalKnapsack(values, weights, capacity):
    # a goes before b when values[a] / weights[a] > values[b] / weights[b],
    # tested as values[a] * weights[b] > values[b] * weights[a] to stay in whole numbers.
    def denser_first(a, b):
        return values[b] * weights[a] - values[a] * weights[b]

    order = sorted(range(len(values)), key=cmp_to_key(denser_first))
    total = 0
    room = capacity
    for i in order:
        if weights[i] <= room:
            total += values[i]  # the whole item fits
            room -= weights[i]
        else:
            total += values[i] * room // weights[i]  # the part that fits, rounded down
            break
    return total

Armadilhas e casos extremos

Ordenar apenas pelo valor ou pelo peso. No primeiro exemplo, o item que vale 90 fica apenas em terceiro lugar por densidade; escolhê-lo primeiro deixa espaço para metade do item que vale 50, totalizando 115 em vez de 151.
Dividir antes de multiplicar. Com valor 13, peso 7 e espaço para 3, 13 / 7 * 3 em aritmética inteira resulta em 3, enquanto 13 * 3 / 7 resulta no valor correto, 5.
Esperar que um item seja fracionado todas as vezes. No terceiro exemplo, todos os itens cabem, e a resposta é a soma de todos os valores, 13.

Perguntas frequentes3

Qual é a complexidade de tempo do problema da mochila fracionária?

Ordenar os itens por valor por peso custa O(n log n) e o preenchimento é feito em uma única passagem, então o total é O(n log n), com espaço O(n) para a ordenação. Procurar o item mais denso a cada rodada custa O(n²).

Por que o algoritmo guloso funciona para a mochila fracionária, mas não para a mochila 0/1?

O corte permite trocar peso de um item menos denso por um mais denso. Sem cortes, um item denso pode deixar espaço que nada mais ocupa. Com valores 8, 11, 15, pesos 2, 3, 4 e capacidade 7, escolher primeiro o mais denso leva os pesos 2 e 4, totalizando 23, enquanto os pesos 3 e 4 totalizam 26. A versão 0/1 exige programação dinâmica.

Como resolver o problema da mochila fracionária sem números de ponto flutuante?

Com pesos positivos, a / b > c / d é o mesmo teste que a × d > c × b, então compare as densidades multiplicando em cruz. O melhor valor é um número inteiro mais uma fração, values[i] × room / weights[i] para o item fracionado, então uma divisão inteira fornece exatamente a resposta arredondada para baixo.

def fractionalKnapsack(values, weights, capacity):
    # Escreva o código aqui

Teste #1

Teste #2

Teste #3

Argumentos

values = [40, 90, 30, 50]
weights = [8, 30, 5, 20]
capacity = 40

Saída Esperada