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

Я работаю со случаем клиента, в котором применяет использовать алгоритм Проблема рюкзака. Я использую код, который я присоединяю, оно функционирует более или менее и у него есть ошибки.

Пример обладает 12 пакетами различных песо (которые в Вашем общем количестве взвешивают 1260 Килограммов) со стоимостью или присоединенной ценой. Цель состоит в том, чтобы загружать максимальное количество пакетов, оказывая предпочтение тем большей стоимости, не превосходя максимального груза грузовика.

Например;

1. - Если максимальный груз грузовика - 9 Килограммов, этот код был бы должен выбирать Paquete 2 Peso :9 valor :160 и нет Paquete 2 Peso :9 valor :150 (Но он это не делает, выбери нуль).

2. - Взамен, если максимальный груз грузовика будет 500 Килограммов, он выберет следующее:

Paquete 9 Peso :230 valor :591
Paquete 3 Peso :153 valor :200
Paquete 4 Peso :50 valor :160
Paquete 2 Peso :9 valor :160
Paquete 1 Peso :9 valor :150

Peso total paquetes: 451
Valor total paquetes: 1261

Он делает работу, но не очень хорошо (ему не хватало бы 7 и 5, чтобы завершать груз 493)

3. - Если максимального груза грузовика будет 230, он выберет следующее:

Paquete 9 Peso :9 valor :230 

Если он делает работу но зло, потому что лучший выбор был бы следующей:

Paquetes 1, 2, 4 y 5
Con un peso peso total de 83
y un valor valor total de 530 

Так как он работоспособнее.

Код:

from itertools import takewhile

#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))

def proceso_valor(item):
    nombre, peso, valor = item
    return float(valor)

def proceso_peso(item):
    nombre, peso, valor = item
    proceso_peso.peso_maximo -= peso
    return proceso_peso.peso_maximo >= 0    

#carga máxima del camión
proceso_peso.peso_maximo = 750


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

sumacarga = 0
sumavalor = 0

for item in carga_lista:
    print item[0] + ' Peso :%i' % item[1] + ' valor :%i' % item[2]
    sumacarga = sumacarga + item[1]
    sumavalor = sumavalor + item[2]

print ''
print 'Peso total paquetes: %i' % sumacarga
print 'Valor total paquetes: %i' % sumavalor

Есть что-то, что я не вижу, нуждаюсь в помощи и вопросы: Что способствует тому, чтобы мой код не функционировал с маленькой стоимостью максимального груза (9 или 100 например)? и: Какой математической операции нет здесь, чтобы улучшать результат?

22
задан 28.02.2016, 04:25
2 ответа

Est проще, чем он кажется: То, чего тебе не хватает, является связью ценой / весом, потому что то, что hacés состоит в том, что функция proceso_valor возвращает тебе только информацию об уравнении: Где ты оставляешь вес?. если то, что querés является максимальным количеством пакетов, оказывая предпочтение тем большей стоимости tenes, что разделять цену по стоимости для того, чтобы sorted возвратил тебе связанный ключ. N или, если я объясняюсь, но то, что tenes, что делать - это:

def proceso_valor(item):
    nombre, peso, valor = item
    return float(valor)/ float(peso)

и я заношу в список, таким образом, sorted вручит тебе твои 4 элемента, где четверть будет этой связью, которую ты ищешь. Если probás с proceso_peso.peso_maximo = 500 вручает тебе груз, равный 493 и не 451, как ты говоришь с двумя пакетами, которых не было.

12
ответ дан 24.11.2019, 14:48

Проблема рюкзака - проблема 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)
3
ответ дан 24.11.2019, 14:48
  • 1
    Est и # 225; достаточно хорошая soluci и # 243; n, хотя я pas и # 243; что по мере того, как увеличил груз м и # 225; xima cami и # 243; n (и #180; PESOMAXIMO и # 180;) увеличивается слишком много время ответа. На 800 нужно убивать процесс, из-за которого много задержка. Давайте ждать какой-то другой ответ, если нет ничего лучшего, я оставляю себе эту. –  Eduardo Munizaga 28.02.2016, 03:21
  • 2
    Я думаю, что ты не понимаешь хорошо природу проблемы. По мере того, как ты увеличиваешься n и # 250; морской окунь элементов, комплексность увеличивается не-линейным способом. Podr и # 237; чтобы помещать тебе soluci и # 243; n осуществимый с programaci и # 243; n деньги и # 225; слюда для случая имения 50 пакетов, но я сомневаюсь, что он ты вразумительный, прежде всего не попробовав улучшать случаи м и # 225; s простые. Я предпочитаю, чтобы ты попытался и, если он не выходит у тебя, что ты задал другой вопрос достигая докуда тебе удалось. Если ты не хочешь думать, ищи из-за knapsack и находить и # 225; s примеры, хотя без ждания чудес. –  ChemaCortes 28.02.2016, 04:25
  • 3
    #191; не быть и # 237; чтобы лучше предлагать soluci и # 243; n подумавшая в programaci и # 243; n деньги и # 225; слюда вместо того, чтобы использовать алгоритм greedy как алгоритм Эдуардо или одна из грубой силы, которая может брать бесконечность времени с большой n и # 250; морской окунь элементов? По крайней мере, алгоритм programaci и # 243; n деньги и # 225; слюда может уменьшать ее ejecuci и # 243; n приблизительно вовремя cuadr и # 225; костариканский –   28.02.2016, 04:30
  • 4
    @ChemaCortes: Два вопроса только для aclara твой комментарий: 1.-и #191; Цюй и # 233; он заставляет тебя думать, что я не понимаю природу проблемы? 2.-и #191; что заставляет тебя думать, что я не хочу думать?. Я верю в то, что комментарий, как комментарий Luiggi Мендосы - достаточно м и # 225; s обоснованный. –  Eduardo Munizaga 28.02.2016, 17:03
  • 5
    Я сожалею о том, что мой комментарий не был совсем удачливым. Что я хочу сказать, что переходить из начального вопроса, где требуется porqu и # 233; побей козырем один c и # 243; я говорю, куда требуется один c и # 243; я говорю, что d и # 233; soluci и # 243; n в обоснованном времени, потребуй целого магистерского класса на Investigaci и # 243; n Операционный, что я не думаю, что он и #233; ste сайт, чтобы иметь ее. Если ты реализуешь новый вопрос с alg и # 250; n алгоритм, который ты протестировал бы, чтобы решать проблему, быть и # 233; довольный тем, что помогает тебе. –  ChemaCortes 28.02.2016, 20:09