Динамическое программирование SPOJ задачи SCUBADIV

Question

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

Вот ссылка: http://www.spoj.pl/problems/SCUBADIV/

Answer 1

Это должно работать, я думаю:

dp[i, j] = minimum weight needed such that we have i litres of oxygen and j litres 
           of nitrogen

dp[0, 0] = 0 and inf everywhere else
for each read cylinder k do
  for i = maxTotalOxygen down to oxygen[k] do
    for j = maxTotalNitrogen down to nitrogen[k]  do
      dp[i, j] = min(dp[i, j],                                       <- do not take cylinder k
                     dp[i - oxygen[k], j - nitrogen[k]] + weight[k])  <- take cylinder k 

Answer is the minimum dp[i, j] such that i >= RequiredOxygen and j >= RequiredNitrogen.

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

Ограничения проблемы очень малы, и я думаю, что это должно работать.

Answer 2

@ Очень хороший ответ, спасибо:)

Однако есть одна загвоздка:

Следующее должно быть удалено:

dp[oxygen[i], nitrogen[i]] = weight[i] for each cylinder i and inf otherwise

И используйте это вместо:

dp[0][0] = 0 and infinity everywhere else

Предыдущий оператор не является допустимым базовым случаем, поскольку позволяет дважды использовать цилиндры.

Как?

Инвариант самого внешнего цикла состоит в том, что в N -й итерации (из k), мы пытаемся для каждого i, j вычислить минимальный вес, который может быть достигнут, чтобы получить по крайней мере i кислорода и j азота , используя только цилиндры с 1 по N (каждый использовался один раз)

Рассмотрим следующий тестовый пример, где требуется 2 кислорода и 2 азота, и у нас есть 2 баллона, один с весом 1 вол 1 и 1, другой - вес 2 быка 2 и 50

2 2

2

1 1 1

2 2 50

Ответ должен быть 50 просто потому, что мы не можемиспользуйте первый цилиндр дважды.

Базовый случай, который я утверждаю неправильно, заполнит d [1] [1] = 1, прежде чем мы даже запустим циклы.Затем цикл начинается с k = 0 (используйте первый цилиндр и посмотрите, поможет ли он в любой записи), тогда d [2] [2] будет равно d [2-1] [2-1] +1 = d [1][1] + 1 = 2

Окончательный ответ будет 2 единицы веса, потому что 1-й цилиндр использовался дважды из-за базового варианта, и это не правильно.