Problema de mochila con restricciones en valores del artículo

Question

Dado $ n $ artículos con pesas $ w_1, ..., w_n $ y valores < Span Class="Math-contenedor"> $ V_1, ..., v_n $ y un límite de peso $ w $ , el propósito sigue maximizando El valor total de los elementos que se llevarán a cabo (al tiempo que excede el límite de peso). Ahora, una nueva restricción es, una vez que se toma un artículo con valor $ v_i $ , todos los artículos cuyo valor es mayor que $ V_I $ también debe tomarse. (Está bien asumir que todos los $ v_i $ son diferentes)

Mi propósito es lograr esto en $ o (n) $ tiempo, y aquí está mi intento (supongamos que la entrada es una matriz $ A $ de tuples $ (w_i, v_i) $ ):

1. Calcular el peso total de los elementos: $ w _ {\ mathrm {total}} \ obtiene \ sum_ {i= 1} ^ n w_i $ ;

2. Mientras $ (w _ {\ mathrm {total}}> w) $ do:

   2.1 $ P \ obtiene $ mediana de valores en $ a $ ;

   2.2 $ r \ obtiene $ artículos cuyo valor es mayor que $ p $ ;

   2.3 $ l \ obtiene un \ setminus r $ ; (Artículos cuyo valor es más pequeño que $ P $ )

   2.4 $ w_r \ obtiene $ $ \ sum_ {a [i] \ in r} w_i $ ;

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

   2.6 $ A \ obtiene R $ ;

3. $ w \ obtiene w- w _ {\ mathrm {total}} $ ; (la capacidad restante)

4. Repetir Paso 2 para la matriz $ l $ , generando la matriz $ l '$ ;

5. devuelve $ l '\ Cup A $ ;

Observe que el algoritmo para encontrar la mediana cuesta tiempo lineal.

Supongo que mi algoritmo cuesta $ O (n) $ Tiempo desde que, por cada iteración en el bucle de cada vez, las mitades del tamaño de entrada, pero no soy 100% seguro de eso. Entonces, ¿este algoritmo realmente cuestan tiempo lineal? Si no, ¿qué enmiendas se pueden hacer, o hay una idea general para diseñar dicho algoritmo que cuesta tiempo lineal? ¡Cualquier ayuda será muy apreciada! :)

Answer 1

Sí, su algoritmo se ejecuta en $ o (n) $ tiempo si usa la mediana del algoritmo mediano de las medias. Puede probarlo para usted mirando su algoritmo y observando que en cada bucle, el tamaño de la matriz que estamos considerando se corta en la mitad. Y el tiempo de ejecución del cuerpo del bucle es $ o (n) $ (si usamos la mediana de medianas y la copia / filtración de matriz es $ O (n) $ de todos modos). Ahora obtenemos la siguiente suma:

$$ \ 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) $$

El $ \ log (n) $ proviene del hecho de que solo puede dividir el tamaño de la matriz $ log ( n) $ veces en mitades hasta que llegue a $ 1 $ (porque $ 2 ^ {\ log (n) }= n $ ). Cada término de la suma expresa el costo de una ejecución del cuerpo de bucle.