Problema da mochila com restrições nos valores do item

Question

dado $ n $ itens com pesos $ w_1, ..., w_n $ e valores < span class="recipiente de matemática"> $ v_1, ..., v_n $ , e um limite de peso $ W $ , a finalidade ainda está maximizando o valor total dos itens a serem transportados (sem exceder o limite de peso). Agora, uma nova restrição é, uma vez que um item com valor $ v_i $ é feito, todos os itens cujo valor é maior que $ v_i $ também deve ser tomado. (Não há problema em supor que todos $ v_i $ são diferentes)

meu objetivo é conseguir isso em $ O (n) $ tempo, e aqui está a minha tentativa (suponha que a entrada seja uma matemática da matriz. -Container "> $ a $ de tuplas $ (w_i, v_i) $ ):

.

.

1. Calcule o peso total dos itens: $ w _ {\ mathrm {total}} \ gets \ sum_ {i= 1} ^ n w_i $ ;

2. Enquanto $ (w _ {\ mathrm {total}}> w) $ Do:

   2.1 $ p \ gets $ p \ gets $ mediana de valores na $ a $ ;

   2.2 $ r \ gets $ cujo valor é maior que $ p $ ;

   2.3 $ l \ gets a \ setminus r $ ; (itens cujo valor é menor que $ P $ )

   2.4 $ w_r \ gets $ $ \ sum_ {[i] \ em r} w_i $ ;

   2.5 $ w _ {\ mathrm {total}} \ gets w_r $ ;

   2.6 $ a \ gets r $ ;

3. $ w \ gets w- w _ {\ mathrm {total}} $ ; (a capacidade restante)

4. repita a etapa 2 para a matriz $ l $ , gerando a matriz $ l '$ $ ;

5. retorna $ l '\ copo A $ ;

Observe que o algoritmo para encontrar a mediana custa tempo linear.

Eu presumo que meu algoritmo custa $ o (n) $ tempo desde então, para cada iteração em cada loop, a metade do tamanho da entrada - mas não sou 100% confiante disso. Então este algoritmo realmente custou tempo linear? Se não, quais são as alterações, ou existe uma ideia geral para projetar tal algoritmo que custa tempo linear? Qualquer ajuda será muito apreciada! :)

Answer 1

Sim, seu algoritmo é executado em $ O (n) $ tempo se você usar a mediana do algoritmo mediana. Você pode provar que consigo mesmo olhando para o algoritmo e observando que em cada loop do tamanho da matriz que estamos considerando é cortado em metade. E o tempo de execução do corpo de loop é $ O (n) $ (se usarmos mediana de medianas e cópia / filtragem da matriz é $ O (n) $ de qualquer maneira). Agora recebemos a seguinte soma:

$$ \ sum_ {i= 0} ^ {\ log (n)} \ frac {n} {2 ^ i} \ leq \ sum_ {i= 0} ^ {\ infty} \ frac {n} {2 ^ i}= n \ cdot \ sum_ {i= 0} ^ {\ infty} \ frac {1} {2 ^ i}= 2n \ in O (n) $$

a $ \ log (n) $ vem do fato de que você só pode dividir o tamanho da matriz $ log ( n) $ vezes em metades até chegar a $ 1 $ (porque $ 2 ^ {\ log (n) }= n $ ). Cada prazo da soma expressa o custo de uma execução do corpo de loop.