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 2º 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))
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