Алгоритм определения максимального удовольствия

Сама проблема может быть найдена здесь. Суть в том, что Бесси едет на американских горках, но у нее головокружение. Какое максимальное количество удовольствия она может иметь, не преодолевая ее "головокружительный предел". Вход состоит из:

"N K L

где N (1 ≤ N ≤ 1000) - это количество секций в данном случае на американских горках; K (1 ≤ K ≤ 500) - это сумма, при которой уровень головокружения Bessies будет снижаться, если она будет закрывать глаза на любом участке езды; и L (1 ≤ L ≤ 300 000) - это предел головокружения, который может терпеть Бесси, - если ее головокружение становится больше, чем L, Бесси заболеет, и это не весело!

Каждая из следующих N строк будет иметь два целых числа:

F D

где F (1 ≤ F ≤ 20) - это увеличение общего веса Bessies, которое получает оболочка, если она держит глаза открытыми в этом разделе, а D (1 ≤ D ≤ 500) - это увеличение ее уровня головокружения, если она держит ее глаза открытыми в этом разделе. Секции будут перечислены в порядке. "

Мой алгоритм для решения этого выглядит следующим образом:

        cin >> N; // sections
        cin >> K; // amount dizziness can go down
        cin >> L; // dizzy ceiling
        belowL = L; // sets the amount of dizzy left

        for (int i = 0; i < N; i++) {
            cout << "\n" << i;
            cin >> F >> D; // fun increase and dizzy increase
            if (D < belowL) {
                if (F >= D) {
                    funTotal += F;
                }
            }
            else {
                belowL -= K;
            }

Однако это не всегда дает правильный результат. В чем проблема? Он должен выбрать забавный вариант, если только он не поставит Бесси на порог болезни. Есть ли лучший способ сделать это?

Ответ 1

Поэтому вместо того, чтобы дать вам код здесь своеобразное объяснение решения проблемы.

Основной подход заключается в решении динамического программирования, поскольку это сводится к тому, что называется проблемой Knapsack. Подумайте об этом так, ее головокружение - это то, сколько она может носить в мешке сразу, и удовольствие - это то, что она хотела бы максимизировать (по сравнению с ценностью "предметов", которые она носит в мешке). Теперь то, что мы хотели бы сделать, это получить наибольшее удовольствие от американских горках (наибольшее значение в мешке), не делая ее слишком головокружительной (переходя "ограничение веса" на мешок).

Итак, теперь вы хотите выбрать, какие части у нее глаза открыты/закрыты (есть ли предмет в мешке или нет). Поэтому простой способ подумать об этом - выбрать максимум обоих вариантов. Если она может держать глаза открытыми, не переступая порог, или просто держать глаза закрытыми. Но теперь проблема меняется, вы видите, если она держит глаза открытыми, ее порог чувствительности будет уменьшаться (проще решить проблемы).

Используя эту информацию, становится проще адаптировать решение для рюкзака к этой проблеме, не используя обратную трассировку или рекурсию.

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

P.S Я был в регионе, где эта проблема была дана и решена, приятно снова увидеть эту проблему.

Ответ 2

Он должен выбрать забавный вариант, если только он не поставит Бесси на порог болезни. Есть ли лучший способ сделать это?

Проблема в том, что вы не максимизируете удовольствие здесь, вы просто мешаете Бесси стать больным. Когда вы дойдете до раздела, который поставит ее над головокружительным ограничением, вы сможете добавить больше удовольствия, обратившись назад и выбрав опцию "не весело" в предыдущем разделе. Скажите, что у вас есть такой ввод, в порядке F D:

Далее, скажем, что она уже близка к головокружению, когда она попадает в первый раздел выше. Вы можете взять забавный вариант в первых двух разделах и получить увеличение F на 6 и увеличение D на 850. Может быть, это наводит ее на предел. Теперь у вас нет другого выбора, кроме как выбрать вариант без забавы для последующих разделов. С другой стороны, если вы возьмете опцию "без забавы" для первых двух разделов, вы можете выбрать забавный вариант для следующих трех и получить увеличение F из 48 для увеличения D только 500.

Ваш текущий алгоритм принимает удовольствие, если соотношение F: D больше 1, и у вас осталось достаточное количество головокружения. Это разумно, но не оптимально. Вероятно, что фиксированное соотношение не даст оптимального решения. Вместо этого вам нужно учитывать преимущества и стоимость каждой опции для каждого раздела.