У меня небольшая задача, и я действительно не знаю, как ее решить:
У меня есть несколько Объектов, которые имеют определенную ценность и вес, я должен решить, что я хочу скрыть, а что нет. Еще одна проблема - это вес, который я тоже должен обдумать из-за своей прогулки по онгу.
Начиная со списка объектов, которые отмечены индексом, стоимостью, весом. С помощью заданного максимального веса я должен определить наиболее достойные объекты, которые не превышают максимальный вес. Объекты могут быть использованы только один раз.
Мне нужно решить проблему с динамическим программированием на python. Индекс строки и индекс столбца показывают до того момента, когда объект (вес) может быть оптимизирован.
Объекты, которые я представляю как пары веса и веса:
Пример: T [3] [5] показывает, например, самую высокую стоимость, которая может быть решена с помощью 3 объектов, максимальный вес которых равен 5.
Если вы не хотите знать только максимальный вес объекта, а также другую информацию, вы также должны сохранить эту запись. В каждой записи T [i] [j] ypu также можно сохранять, есть ли наивысшая ценность или нет (с 1 или 0), потому что в каждой строке может существовать только один объект. Эти флаги также можно использовать для заполнения таблицы. Поэтому функция bestChoice (диаграмма, элемент) есть. Измените функцию createChart (items, MAX), чтобы записи в таблицах могли вычислять пары из значения createChart и объясненных флагов (0 или 1).
Построенная таблица T2 может с помощью функции bestChoice вернуть список объектов. Реализуйте функцию так, чтобы возвращаемые значения были списком, который возвращает 0 или 1 для объектов, и если это в разделе или нет.
Я знаю, что задача сложная. Если у вас есть вопрос в задании, пожалуйста, спросите. Заранее спасибо.
def createChart( items , MAX ):
#Here should be the solution for creating a chart T from a given list of objects and maximum weight
return ?
def bestChoice( chart , items ):
return ? #the selection of items should be returned here
#Testcase
items = [(3,4),(1,1),(4,5),(3,4),(2,2)]
maxWeight = 8
T = createChart( items , MAX )
# T should be this
#[[(0, 0) (0, 0) (0, 0) (0, 0) (0, 0) (0, 0) (0, 0) (0, 0) (0, 0)],
# [(0, 0) (0, 0) (0, 0) (0, 0) (3, 1) (3, 1) (3, 1) (3, 1) (3, 1)],
# [(0, 0) (1, 1) (1, 1) (1, 1) (3, 0) (4, 1) (4, 1) (4, 1) (4, 1)],
# [(0, 0) (1, 0) (1, 0) (1, 0) (3, 0) (4, 0) (5, 1) (5, 1) (5, 1)],
# [(0, 0) (1, 0) (1, 0) (1, 0) (3, 0) (4, 0) (5, 0) (5, 0) (6, 1)],
# [(0, 0) (1, 0) (2, 1) (3, 1) (3, 0) (4, 0) (5, 0) (6, 1) (7, 1)]]
#first component of the the last table item
bestValue = T[-1][-1][0] #should return the maximal value ( = 7 )
L = bestChoice( T , items)
#should be [0, 1, 1, 0, 1]