В каждом отдельном примере, который я нашел для задачи о рюкзаке 1/0 с использованием динамического программирования, где элементы имеют веса (затраты) и прибыль, никогда не говорится явно о сортировке списка элементов, но во всех примерах они сортируются путем увеличения обоих вес и прибыль (в примерах больший вес дает более высокую прибыль). Итак, мой вопрос: при добавлении элементов в матрицу из массива / списка элементов, могу ли я добавлять их в любом порядке или добавлять элементы с наименьшим весом или прибылью? Потому что из нескольких примеров я обнаружил, что не уверен, что это просто совпадение или вам действительно нужно каждый раз вводить в матрицу наименьший вес / прибыль.
Вам нужно отсортировать входные данные для рюкзака динамического программирования
comment
Нет, сортировка входных данных для задачи о ранце не требуется. Если это сделано, то это делается только для иллюстрации решения. Вы можете попробовать запустить его после ввода в любом порядке, и результат должен быть таким же.
- person Ram Narasimhan schedule 24.04.2015
Ответы (4)
Решение динамического программирования - это не что иное, как выбор всех возможностей (грубая сила) эффективным способом (просто путем их сохранения) ... Примечание. Мы рассматриваем все подмножества ... Теперь, если список отсортирован или нет, общее количество подмножества будут такими же, как и подмножества, и в конце будут рассмотрены все подмножества .. Так что более или менее, даже если список имеет любой порядок, это не имеет значения ...
person
Shubham Sharma
schedule
27.04.2015
Нет, вам не нужно сортировать веса, потому что каждая строка дает максимально возможное значение ниже ограничения веса этой строки. Максимум будет в последнем столбце этой строки.
person
Shruti Gupta
schedule
26.12.2017
Возможно, вы ищете динамические решения снизу вверх. И в динамическом решении есть одна характеристика, когда вы решаете, используя метод снизу вверх.
«Второй подход - это восходящий метод. Этот подход обычно зависит от некоторого естественного понятия« размера »подзадачи, так что решение любой конкретной подзадачи зависит только от решения« меньших »подзадач. Мы сортируем подзадачи по размеру и решайте их в порядке размера, начиная с наименьшего. При решении конкретной подзадачи мы уже решили все более мелкие подзадачи, от которых зависит ее решение, и сохранили их решения. Мы решаем каждую подзадачу только один раз, и когда мы впервые ее видим, мы уже решили все его предварительные подзадачи ".
Из, Введение в алгоритм, CORMEN (3-е издание)
person
Django
schedule
11.12.2016
Меньшая проблема в этом случае просто меньше с точки зрения количества доступных элементов на выбор, а не с точки зрения прибыли или веса этих элементов. Если дан список из 3 пунктов, подзадачи будут 2 пунктами и одним пунктом на выбор.
Самая маленькая проблема сначала жестко запрограммирована (базовый случай), затем на каждом этапе перехода от меньшей проблемы к большей перечисляется лучшая прибыль и выбирается максимальная. В конце концов, все комбинации 2 ^ n были бы рассмотрены, и различные этапы повторного максимума будут пузыриться наибольшим решением.
Изменение порядка ввода или размещение доминирующих элементов во входных данных (например, более высокий вес и меньшая прибыль) может просто изменить, какой аргумент max () выигрывал на каждом этапе, но окончательный максимальный результат будет получен из того же выбора элементов, хотя и будет выбираются на разных этапах алгоритма для разных порядков сортировки или входных характеристик.
person
Han Qi
schedule
19.10.2020
