Динамическое программирование?

Question

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

Answer 1

Это не изящное решение, но оно будет работать для этой конкретной проблемы (я предполагаю, у нас такой же профессор).

Логика заключается в том, что для каждого V [n] [c] мы хотим найти максимально возможное значение для каждой единицы валюты, и для этого мы должны вычислить максимальное значение из 6 значений.

Существует 6 значений, так как существует 3 валюты, и каждая из этих валют имеет два возможных способа, которыми она может быть конвертирована в целевую валюту.

В этом случае, поскольку есть только 2 обмена, я просто делаю два утверждения, а не другой цикл. Это представлено 0 в массиве: скорости [0] [i] [c]

Надеюсь, это поможет!

for (int n = 1; n <= numberOfTransactions; n++) { 
     for (int c = 0; c < numberOfcurrencies; c++) { 
      double max = Double.NEGATIVE_INFINITY; 
      double temp; 
      for (int i = 0; i < numberOfcurrencies;i++) { 
       temp = rates[0][i][c]*V[n-1][i]; 
       if (temp > max) 
        max = temp; 
       temp = rates[1][i][c]*V[n-1][i]; 
       if (temp > max) 
        max = temp; 
      } 
      V[n][c] = max; 
     } 
    }