Mochila ilimitada (Se permite la repetición de artículos) | conjunto 2

Dado un entero W , los arreglos val[] y wt[] , donde val[i] y wt[i] son ​​los valores y pesos del i -ésimo elemento, la tarea es calcular el valor máximo que se puede obtener usando pesos no superior a W.
Nota: cada peso se puede incluir varias veces.

Ejemplos:

Entrada: W = 4, val[] = {6, 18}, wt[] = {2, 3}
Salida: 18
Explicación: El valor máximo que se puede obtener es 18, seleccionando el elemento dos veces.

Entrada: W = 50, val[] = {6, 18}, wt[] = {2, 3}
Salida: 294

Enfoque ingenuo: consulte la publicación anterior para resolver el problema utilizando el algoritmo tradicional de mochila ilimitada.
Complejidad temporal: O(N * W)
Espacio auxiliar: O(W)

Enfoque eficiente:  el enfoque anterior se puede optimizar en función de las siguientes observaciones:

  • Supongamos que el i -ésimo índice nos da el valor máximo por unidad de peso en los datos dados, que se puede encontrar fácilmente en O(n) .
  • Para cualquier peso X , mayor o igual que wt[i] , el valor máximo alcanzable será dp[X – wt[i]] + val[i] .
  • Podemos calcular los valores de dp[] de 0 a wt[i] usando el algoritmo tradicional y también podemos calcular el número de instancias de i -ésimo elemento que podemos incluir en peso W.
  • Entonces, la respuesta requerida será val[i] * (W/wt[i]) + dp[W%wt[i]] .
     

A continuación se muestra la implementación del nuevo algoritmo.

Python3

# Python Program to implement the above approach
  
from fractions import Fraction
  
# Function to implement optimized
# Unbounded Knapsack algorithm
def unboundedKnapsackBetter(W, val, wt):
  
    # Stores most dense item
    maxDenseIndex = 0
  
    # Find the item with highest unit value
    # (if two items have same unit value then choose the lighter item)
    for i in range(1, len(val)):
          
      if Fraction(val[i], wt[i]) \
            > Fraction(val[maxDenseIndex], wt[maxDenseIndex]) \
             or (Fraction(val[i], wt[i]) == Fraction(val[maxDenseIndex], wt[maxDenseIndex]) \
             and wt[i] < wt[maxDenseIndex] ):
                   
        maxDenseIndex = i
  
    dp = [0 for i in range(W + 1)]
  
    counter = 0
    breaked = False
    for i in range(W + 1):
        for j in range(len(wt)):
              
            if (wt[j] <= i):
                dp[i] = max(dp[i], dp[i - wt[j]] + val[j])
                  
        if i - wt[maxDenseIndex] >= 0 \
            and dp[i] - dp[i-wt[maxDenseIndex]] == val[maxDenseIndex]:
                  
            counter += 1
              
            if counter>= wt[maxDenseIndex]:
                  
                breaked = True
                # print(i)
                break
        else:
            counter = 0
  
    if not breaked:
        return dp[W]
    else:
        start = i - wt[maxDenseIndex] + 1
        times = (W - start) // wt[maxDenseIndex]
        index = (W - start) % wt[maxDenseIndex] + start
        return (times * val[maxDenseIndex] + dp[index])
          
          
# Driver Code
W = 100
val = [10, 30, 20]
wt = [5, 10, 15]
   
print(unboundedKnapsackBetter(W, val, wt))
Producción:

300

Complejidad de tiempo : O( N + min(wt[i], W) * N)
Espacio auxiliar: O(W)

Publicación traducida automáticamente

Artículo escrito por zhangyijun396 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *