Блог

Главная - Вопросы по программированию - Выбор элементов с наибольшим значением в списке в правильном порядке

Выбор элементов с наибольшим значением в списке в правильном порядке

#python #list #for-loop #knapsack-problem #branch-and-bound

#python #Список #for-цикл #проблема с рюкзаком #переход с привязкой

Вопрос:

Я решаю проблему с рюкзаком, используя алгоритм ветвления и привязки, над которым я работаю прямо сейчас. В алгоритме я хотел начать выбирать элементы с наибольшей плотностью (значение / вес). Я создал список с именем «плотность» и произвел необходимые вычисления. Мне нужно каждый раз выбирать максимальное значение из этого списка. Но каждый раз, когда я пытаюсь, порядок смешивается. Мне нужно обновить переменную «a», потому что каждый раз, когда я удаляю элемент, список становится на один меньше. Но не смог понять, как его обновить. Мне нужна помощь в выборе элементов в правильном порядке.

вес, значение, плотность — это списки. вместимость и комната — это целочисленные значения, указанные в задаче. Это список плотности.

введите описание изображения здесь

Я хочу получить индекс максимального элемента в этом списке. Затем вычтите его «вес» из «емкости», чтобы определить, сколько «места» осталось. И добавьте «значение» к «самому высокому», чтобы в рюкзаке можно было добавить наибольшее значение. После того, как я сделал это для первого элемента, повторяйте его до тех пор, пока не останется совсем мало места.

     def branch_n_bound(value,weight,capacity):
        global highest,size
        size=0
        room=capacity
        density = [0] * len(items)
        highest = 0
        for i in range(n):
            density[i] = val[i] / weight[i]
        for i in range(n):
            a=density.index(max(density))
            if weight[a]<=room:
                room-=weight[a]
                highest =value[a]
                size =weight[a]
                taken[a]=1
                del density[a], weight[a], value[a]
            else:
                break

Комментарии:

1. Вместо вашей del density[a], ... строки попробуйте density.pop(a) , weight.pop(a) и value.pop(a) , каждый в своей строке.

2. Кроме того, если вы предоставите образцы данных и ожидаемый результат, а также то, что вы получаете и почему это неправильно, мы сможем вам лучше помочь.

3. @Engineero Я пробовал это, но, к сожалению, не сработало. Я добавил дополнительный комментарий, чтобы сделать его более понятным.

Ответ №1:

Я думаю, что проблема, которую вы пытаетесь решить, может быть решена проще с изменением структуры данных. Вместо построения массива плотности вы можете создать массив кортежей [(density, weight, value)...] и основывать свое решение на этом массиве. Если вы не хотите использовать так много дополнительной памяти и предполагаете, что вы согласны с изменением входных данных, вы можете пометить свои индексы как удаленные — например, вы можете установить значение, вес и плотность во что-то отрицательное, чтобы знать, что данные были удалены из этого индекса.

Вы также можете взглянуть на структуру данных heapq: https://docs.python.org/3/library/heapq.html . Вы можете работать с кучей, чтобы извлечь максимум, и сохранять индексы в этой куче.