# A naive recursive implementation of 0-1 Knapsack Problem # Returns the maximum value that can be put in a knapsack of # capacity W def knapSack(W, wt, val, n): # Base Case if n == 0 or W == 0 : return 0 # If weight of the nth item is more than Knapsack of capacity # W, then this item cannot be included in the optimal solution if (wt[n-1] > W): return knapSack(W, wt, val, n-1) # return the maximum of two cases: # (1) nth item included # (2) not included else: return max(val[n-1] + knapSack(W-wt[n-1], wt, val, n-1), knapSack(W, wt, val, n-1)) # end of function knapSack # To test above function val = [60, 100, 120] wt = [10, 20, 30] W = 50 n = len(val) print knapSack(W, wt, val, n) # This code is contributed by Nikhil Kumar Singh
Producción:
220
# A Dynamic Programming based Python # Program for 0-1 Knapsack problem # Returns the maximum value that can # be put in a knapsack of capacity W def knapSack(W, wt, val, n): K = [[0 for x in range(W + 1)] for x in range(n + 1)] # Build table K[][] in bottom up manner for i in range(n + 1): for w in range(W + 1): if i == 0 or w == 0: K[i][w] = 0 elif wt[i-1] <= w: K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]) else: K[i][w] = K[i-1][w] return K[n][W] # Driver program to test above function val = [60, 100, 120] wt = [10, 20, 30] W = 50 n = len(val) print(knapSack(W, wt, val, n)) # This code is contributed by Bhavya Jain
Producción:
220
Consulte el artículo completo sobre programación dinámica | ¡ Establezca 10 (0-1 Problema de mochila) para obtener más detalles!
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA