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

Question

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

"NKL

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

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

FD

где 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; 
      } 

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

Answer 1

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

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

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

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

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

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

Answer 2

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

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

1 400 
5 450 
10 25 
18 75 
20 400 

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

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