Как реализовать дерево состояний пространства?

Question

Я пытаюсь решить такой рюкзак как проблема от MIT OCW. Задача проблемы 5.

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

Если я нахожу узел, где бюджета недостаточно, я должен остановиться здесь. Должен ли я добавлять атрибут к каждому узлу дерева?

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

У вас есть идея? Не могли бы вы реализовать его в python?

Answer 1

Я надеюсь, что я правильно понял проблему, если не направляйте меня :)
(извините за путаницу, вытекающий из двух различных значений «состояния»)

Вы, конечно, можете добавить атрибут в node (это часть состояния!), так как это очень маленький объем данных. Имейте в виду, что это не обязательно, чтобы сохранить его, поскольку он неявно присутствует в остальной части состояния (учитывая состояния, которые вы уже выбрали, вы можете вычислить его). Лично я бы добавил атрибут, потому что нет смысла его вычислять много раз.

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

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