http://projecteuler.net/index.php?section=problems&id=18
OK so a triangle.. of costs.. and you need to find the most expensive way across it… so the best way is to work backwards from all possible endings and calculate the most expensive way to get there.
A simple example
1
2 5
7 3 5
Ending positions are 7,3,5,6…
To get to 7 we can have arrived from 2 or 5.. the most expensive route would be 5+7=13
To get to 3 we can have either come from 2 or 5.. the most expensive route would be 3+5 = 8..
etc to get a new triangle of max routes which looks like this..
11
9 10
7 3 5
giving us the answer of 11… for the most expensive path thru the triangle….. so repeat this formula for any size of triangle.. using code as follows:
______________________
static void Main(string[] args)
{
int[,] a= new int[15,15];
a[0,0]=75;
a[0,1]=95; a[1,1]=64;
a[0,2]=17; a[1,2]=47; a[2,2]=82;
a[0,3]=18; a[1,3]=35; a[2,3]=87; a[3,3]=10;
a[0,4]=20; a[1,4]=04; a[2,4]=82; a[3,4]=47; a[4,4]=65;
a[0,5]=19; a[1,5]=01; a[2,5]=23; a[3,5]=75; a[4,5]=03; a[5,5]=34;
a[0,6]=88; a[1,6]=02; a[2,6]=77; a[3,6]=73; a[4,6]=07; a[5,6]=63; a[6,6]=67;
a[0,7]=99; a[1,7]=65; a[2,7]=04; a[3,7]=28; a[4,7]=06; a[5,7]=16; a[6,7]=70; a[7,7]=92;
a[0,8]=41; a[1,8]=41; a[2,8]=26; a[3,8]=56; a[4,8]=83; a[5,8]=40; a[6,8]=80; a[7,8]=70; a[8,8]=33;
a[0,9]=41; a[1,9]=48; a[2,9]=72; a[3,9]=33; a[4,9]=47; a[5,9]=32; a[6,9]=37; a[7,9]=16; a[8,9]=94; a[9,9]=29;
a[0,10]=53; a[1,10]=71; a[2,10]=44; a[3,10]=65; a[4,10]=25; a[5,10]=43; a[6,10]=91; a[7,10]=52; a[8,10]=97; a[9,10]=51; a[10,10]=14;
a[0,11]=70; a[1,11]=11; a[2,11]=33; a[3,11]=28; a[4,11]=77; a[5,11]=73; a[6,11]=17; a[7,11]=78; a[8,11]=39; a[9,11]=68; a[10,11]=17; a[11,11]=57;
a[0,12]=91; a[1,12]=71; a[2,12]=52; a[3,12]=38; a[4,12]=17; a[5,12]=14; a[6,12]=91; a[7,12]=43; a[8,12]=58; a[9,12]=50; a[10,12]=27; a[11,12]=29; a[12,12]=48;
a[0,13]=63; a[1,13]=66; a[2,13]=04; a[3,13]=68; a[4,13]=89; a[5,13]=53; a[6,13]=67; a[7,13]=30; a[8,13]=73; a[9,13]=16; a[10,13]=69; a[11,13]=87; a[12,13]=40; a[13,13]=31;
a[0,14]=04; a[1,14] = 62; a[2,14] = 98; a[3,14] = 27; a[4,14] = 23; a[5,14] = 09; a[6, 14] = 70; a[7, 14] = 98; a[8, 14] = 73; a[9,14] = 93; a[10, 14] = 38; a[11, 14] = 53; a[12, 14] = 60; a[13, 14] = 04; a[14, 14] = 23;
//start at the last row - work back to top of triangle from all end possibilities
for (int row = 13; row > -1; row--)
{
//now work thru all the columns
for (int col = 0; col < 14; col++)
{
//find in the row below the max val possible from option1 or option 2 (l or r linked cell)
if (a[col,row+1] > a[col + 1,row+1])
{
a[col,row] = a[col,row+1] + a[col,row];
}
else
{
a[col,row] = a[col+1, row+1] + a[col,row];
}
}
}
Console.WriteLine(a[0,0]);
Console.ReadLine();
}
No comments:
Post a Comment