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

Jude Savio спросил: 12 мая 2018 в 04:15 в: java

В городе есть N улиц, и на каждой улице есть одна сокровищница с определенным количеством золотых монет - C (1) .... C (N) в ней. Поскольку разбойник умный, чтобы не попасться, если он рубит в доме на данной улице, он не грабит в домах на двух улицах, которые примыкают к дому, ограбленному (либо слева, либо справа). Таким образом, он избегает осознания среди людей, и его риск уменьшается. Учитывая, что N и монеты C (i) (где i = 1 - N) в каждой из сокровищницы, найдите максимальные золотые монеты M, которые может приобрести грабитель.

import java.util.Scanner;public class MaximiseRobbery { public static void main(String[] args) {
  Scanner scan = new Scanner(System.in);
  int houses = scan.nextInt();
  int[] amPerHouse = new int[houses];
  for (int i = 0; i < houses; i++) {
   amPerHouse[i] = scan.nextInt();
  }
  int maximumRobbery = maximizeRobbery(amPerHouse, houses);
  System.out.println(maximumRobbery);
  scan.close();
 } private static int maximizeRobbery(int[] amPerHouse, int houses) {
  if (houses == 1) {
   return amPerHouse[0];
  } else if (houses == 2) {
   return Math.max(amPerHouse[0], amPerHouse[1]);
  }
  int[] dp = new int[amPerHouse.length];
  dp[0] = amPerHouse[0];
  dp[1] = amPerHouse[1];
  for (int i = 2; i < houses; i++) {
   dp[i] = Math.max(dp[i - 2] + amPerHouse[i], dp[i - 1]);
  }
  return dp[houses - 1];
 }
}

для ввода:

7
10 20 15 1 9 12 5

вывод:

32

, но в соответствии с приведенной выше реализацией полученный результат равен 39

также для ввода:

10
5 6 6 16 30 15 13 16 19 27

вывод:

63

, но в соответствии с вышеизложенным результатом получается 84

1 ответ

Есть решение
NiVeR ответил: 12 мая 2018 в 04:58

Я думаю, что вы не поняли это утверждение правильно. Что это говорит, ИМО, заключается в том, что если вы ограбите дом на улице i, вы не сможете ограбить дома на 2-х улицах слева, поэтому i-1 и i-2, а на 2-х улицах справа, поэтому i+1 и i+2. Изменение в соответствии с этим должно заставить его работать. Действительно, в первом примере ограбленные дома находятся в индексах 1 и 5, поэтому sum = 20 + 12 = 32.

Jude Savio ответил: 12 мая 2018 в 05:39
Подумал, так что
NiVeR ответил: 12 мая 2018 в 05:43
Wellcome. Если это поможет, примите ответ.