Проблема с Проблемой рюкзака

Проблема рюкзака - проблема NP, или же, ты не будешь находить алгоритм, который получал бы всегда оптимальное решение. Тем не менее, что да, которое ты можешь делать, состоит в том, чтобы отказываться от случаев, которые хуже ведут себя, чтобы оставлять себе лучшие возможные решения.

Выражение ésto, твой алгоритм был бы должен у него есть две цели:

1. Помещать самое большее число пакетов
2. Между полученными решениями, оставлять себе тех, которые погружают большую стоимость

В твоем планировании он не остается ясным, если первенствовать из-за стоимости значит помещать сначала самые дорогие пакеты, или что полная сумма самая высокая. Я предполагаю, что это вышеупомянутый случай. Хотя проблема также может быть выдвинутой наоборот: хотеть принести самый дорогой груз, не превосходя предела груза грузовика.

Ну вот, твой алгоритм начинается из-за того, что упорядочивает из-за стоимости и после оставлять себе тех, которые помещаются в максимальном грузе. Umm! Справедливая противоположность, во что ты был бы должен пытаться. Чтобы начинаться, ты уменьшаешь все дорогие пакеты максимального груза. Например, попытайся с двумя пакетами:

proceso_peso.peso_maximo = 750

PAQUETES = (
    ("Paquete 1", 9, 150), ("Paquete 2", 1000, 10000)
    )

carga_lista = list(takewhile(proceso_peso, reversed(sorted(PAQUETES, key=proceso_valor))))

Пакет у 2 есть много стоимость и много веса. Подтвердив с proceso_peso ты уменьшаешь Ваш вес в proceso_peso.peso_maximo, что дает негатив, и takewhile закончи тем, что возврати пустой список.

Однажды я одеваю неудачу, мой совет состоит в том, чтобы ты не использовал признаки функции и, важнее, ты не изменил условия проблемы внутри iteracción (и если ты это делаешь, что оказался ясным). Для первого, используй программирование ориентируй объекты; для второго, используй функциональное программирование. Для обеих вещей, используй python.

Проблема рюкзака достаточно заучена. Конечно, что ты находишь несколько алгоритмов, которые пробуют встретить решения более или менее быстрого способа. Если он служит тебе отпечатком, я помещаю тебе, как он был бы сделан "грубой силой", хотя он опаздывает очень много времени в каких-то случаях:

from operator import itemgetter

#Paquetes: "Nombre del paquete", Kilos, Precio
PAQUETES = (
    ("Paquete 1", 9, 150), ("Paquete 2", 9, 160), ("Paquete 3", 153, 200), ("Paquete 4", 50, 160),
    ("Paquete 5", 15, 60), ("Paquete 6", 66, 45), ("Paquete 7", 27, 60), ("Paquete 8", 39, 40),
    ("Paquete 9", 230, 591), ("Paquete 10", 520, 10), ("Paquete 11", 110, 70), ("Paquete 12", 32, 30))

#carga máxima del camión
PESOMAXIMO = 230

# Útiles para acceso al peso y valores (irían mejor definiendo una clase)
get_peso = itemgetter(1)
get_valor = itemgetter(2)

def total_peso(paquetes):
    return sum(get_peso(x) for x in paquetes)

def total_valor(paquetes):
    return sum(get_valor(x) for x in paquetes)

# Obtención de todas las combinaciones posibles
# Función recursiva
def combinaciones(paquetes, peso_maximo):
    paqs = [ p for p in paquetes if get_peso(p) <= peso_maximo ]
    resultado = []
    for p in paqs:
        res = combinaciones([x for x in paqs if x!=p], peso_maximo - get_peso(p))
        if len(res) == 0:
            resultado.append([p])
        else:
            resultado.extend([[p]+x for x in res])
    return resultado

# solución
max(combinaciones(PAQUETES, PESOMAXIMO), key=total_valor)