Я пытаюсь получить максимальную сумму от вершины до низа входного треугольника, которая должна быть такой
5
94 48
95 30 96
77 71 26 67
97 13 76 38 45
07 36 79 16 37 68
48 07 09 18 70 26 06
18 72 79 46 59 79 29 90
20 76 87 11 32 07 07 49 18
27 83 58 35 71 11 25 57 29 85
14 64 36 96 27 11 58 56 92 18 55
02 90 03 60 48 49 41 46 33 36 47 23
92 50 48 02 36 59 42 79 72 20 82 77 42
56 78 38 80 39 75 02 71 66 66 01 03 55 72
44 25 67 84 71 67 11 61 40 57 58 89 40 56 36
85 32 25 85 57 48 84 35 47 62 17 01 01 99 89 52
06 71 28 75 94 48 37 10 23 51 06 48 53 18 74 98 15
27 02 92 23 08 71 76 84 15 52 92 63 81 10 44 10 69 93
Вывод должен быть:
Maximum total: 1320
Path (for example) : 55 - 48 -30 - etc
Путь должен быть числом, которое я сложил вместе, чтобы получить результат 1320. Я могу найти СУММУ (1320), но я не могу найти способ найти все числа, которые были суммированы. Мой код возвращает все числа, а не только те, которые были суммированы.
static void Sum()
{
int[,] list = new int[18, 19];
int[,] list2 = new int[18, 19];
string input = @"55
94 48
95 30 96
77 71 26 67
97 13 76 38 45
07 36 79 16 37 68
48 07 09 18 70 26 06
18 72 79 46 59 79 29 90
20 76 87 11 32 07 07 49 18
27 83 58 35 71 11 25 57 29 85
14 64 36 96 27 11 58 56 92 18 55
02 90 03 60 48 49 41 46 33 36 47 23
92 50 48 02 36 59 42 79 72 20 82 77 42
56 78 38 80 39 75 02 71 66 66 01 03 55 72
44 25 67 84 71 67 11 61 40 57 58 89 40 56 36
85 32 25 85 57 48 84 35 47 62 17 01 01 99 89 52
06 71 28 75 94 48 37 10 23 51 06 48 53 18 74 98 15
27 02 92 23 08 71 76 84 15 52 92 63 81 10 44 10 69 93";
var charArray = input.Split('\n');
for (int i = 0; i < charArray.Length; i++)
{
var numArr = charArray[i].Trim().Split(' ');
for (int j = 0; j < numArr.Length; j++)
{
int number = Convert.ToInt32(numArr[j]);
list[i, j] = number;
list2[i, j] = number;
}
}
StringBuilder path = new StringBuilder();
for (int i = 16; i >= 0; i--)
{
for (int j = 0; j < 18; j++)
{
//list[i, j] = Math.Max(list[i, j] + list[i + 1, j], list[i, j] + list[i + 1, j + 1]);
if (list[i, j] + list[i + 1, j] > list[i, j] + list[i + 1, j + 1])
{
if (list2[i, j] > 0)
path.Append(list2[i, j] + " - ");
if (list2[i+1, j] >0)
path.Append(list2[i+1, j] + " - ");
list[i, j] = list[i, j] + list[i + 1, j];
}
else
{
//path.Append(list2[i, j] + " - " + list2[i + 1, j + 1]+ " - ");
if (list2[i, j] > 0)
path.Append(list2[i, j] + " - ");
if (list2[i + 1, j] > 0)
path.Append(list2[i + 1, j] + " - ");
list[i, j] = list[i, j] + list[i + 1, j + 1];
}
}
}
Console.WriteLine(string.Format("Maximum total: {0} \n Path {1}", list[0, 0], path));
Я пытался в течение 4 дней решить эту проблему в течение 4 дней, но мне это не удалось, я ценю вашу помощь. Спасибо
list[0,0]
. Куда вы там ходите?list[1,0]
, так как это значение больше (1265 против 1130). Обратите внимание на индекс и извлеките значение изlist2
, которое имеет исходные значения. От 1265 куда вы идете? 1171. Снова используйте этот индекс, чтобы найти значение вlist1
. Продолжайте делать это, пока не доберетесь до дна, и у вас будет свой путь. 21.11.2019