Problema de mochila con elementos duplicados -- python campo con knapsack-problem camp codereview Relacionados El problema

Knapsack problem with duplicate elements


3
vote

problema

Español

Resolví el problema de la mochila donde se permiten los elementos duplicados:

Pesos y valores dados relacionados con los artículos n y la capacidad máxima permitida para estos artículos. ¿Cuál es el valor máximo que podemos lograr si podemos elegir cualquier peso en cualquier número de veces para un peso total permitido de W?

Entrada:

w = 10

peso = [2,3,6,4]

costo = [3,4,6,10]

Salida:

23

He escrito este código. ¿Hay alguna forma de mejorarlo?

  pop0  
Original en ingles

I solved the knapsack problem where duplicates elements are allowed:

Given weights and values related to n items and the maximum capacity allowed for these items. What is the maximum value we can achieve if we can pick any weights any number of times for a total allowed weight of W?

input:

W = 10

weight = [2,3,6,4]

cost = [3,4,6,10]

output:

23

I have written this code. Is there any way to improve it?

def knapsack(W, weight, cost):     #import pdb; pdb.set_trace()     table = [0] * (W+1)     for w in xrange(W+1):         max_so_far = 0         for i, wt in enumerate(weight):             if wt <= w:                 cur = cost[i] + table[w-weight[i]]                 if cur > max_so_far:                     max_so_far = cur         table[w] = max_so_far     print table         return table[W]  weight = [2,3,6,4] cost = [3,4,6,10] print knapsack(10,weight,cost) 
     
     
     

Lista de respuestas

1
 
vote
  • T3 es un nombre sin sentido para una estructura de datos importante. Debe explicarse por un comentario al menos.
  • T4 y T5 Parezca lo suficientemente similar para causar confusión.
  • En lugar de usar T6 , puede iterar sobre T7 y evitar la indexación.
  • El T8 fue conveniente para computar un máximo. El bucle interno T9 se puede convertir en una expresión del generador para T top() const0 para procesar. Sin embargo, T top() const1 eleva un error si no hay artículos para procesar. En las versiones recientes de Python, se puede administrar un valor predeterminado a T top() const2 para evitar eso.

Mi reescritura para Python 3.4 o posterior (veo que está utilizando Python 2.x):

  T top() const3  
 
  • table is a meaningless name for an important data structure. It should be explained by a comment at least.
  • W and w look similar enough to cause confusion.
  • Instead of using enumerate, you could iterate over zip(weight, cost) and avoid indexing.
  • The max builtin function is convenient for computing a maximum. The inner for loop can be converted to a generator expression for max to process. However, max raises an error if there are no items to process. In recent versions of Python a default value can be given to max to avoid that.

My rewrite for Python 3.4 or later (I see you are using Python 2.x):

def knapsack(W, weights, costs):     '''Given weights and costs of items, compute maximum cost for total     allowed weight W when any item can be picked any number of times.     '''     best = [0] # best[x] is the max cost for allowed weight x     for capacity in range(1, W + 1):         best.append(max((cost + best[capacity - weight]                          for weight, cost in zip(weights, costs)                          if weight <= capacity),                         default=0))     return best[W] 
 
 

Relacionados problema

4  Averigüe la cantidad de computadoras portátiles que Molly puede comprar en función de el dinero disponible, la matriz de cantidades y la matriz de costos  ( Find out how many laptops molly can buy based on available money array of quant ) 
Descripción del problema: Molly quiere comprar computadoras portátiles para su escuela. Averigüe la cantidad de computadoras portátiles que puede comprar c...

3  Problema de Knapsack01, escrito en C #  ( Knapsack01 problem written in c ) 
¿Este código está escrito en un estilo decente? Aprecie algunos comentarios :) ShopItemCategory4 ...

3  Código para dividir los regalos por igual  ( Code for dividing gifts equally ) 
Recientemente me encontré con este problema : Es el cumpleaños de Lavanya y varias familias han sido invitadas a la fiesta de cumpleaños. Como es habitu...

6  Python Knapsack codicioso  ( Python knapsack greedy ) 
Dado un diccionario de vacas y su peso: cows = {'Betsy': 9, 'Oreo': 6, 'Herman': 7, 'Florence': 2, 'Maggie': 3, 'Moo Moo': 3, 'Milkshake': 2, 'Lola': 2, 'M...

1  Solución de Knapsack 01  ( Knapsack 01 solution ) 
Solución para el problema de Knapsack 01 delimitado. Una vez más, la descripción completa es difícil en este espacio, consulte aquí . Buscando revisión de có...

0  La solución al problema de Knapsack supera los límites de tiempo y RAM  ( Solution to knapsack problem exceeds time and ram limits ) 
Mi objetivo es codificar la problema de mochila algoritmo. El problema es que una mochila tiene un límite de peso dado, ## result vector HLClist<-vecto...

56  Solución de mochila de programación dinámica  ( Dynamic programming knapsack solution ) 
Escribí una solución a la problema de mochila en Python, utilizando un algoritmo de programación dinámico de abajo hacia arriba. Calcula correctamente el va...

2  0-1 problema de mochila - Implementación  ( 0 1 knapsack problem implementation ) 
Dado un conjunto de artículos con un peso y un valor, este problema proporciona el subconjunto de elementos que maximizan el valor para que sus pesos combinad...

3  Implementación de problemas de suministro de subconjunto  ( Subset sum problem implementation ) 
Aquí hay una implementación recursiva de la problema de suma de subconjunto : using System; namespace Exercise { class SubsetSum { static void Ma...

3  Knapsack 0-1 en óxido  ( Knapsack 0 1 in rust ) 
Aquí hay una implementación de mochila en óxido. ¿Cómo puede ser mejorado? Algunas cosas que ya he visto: ¿Cuál sería la mejor manera de extraer el resultad...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos