0

i tried going through a row while it's sum is higher than the column's and switching them that way but i kinda failed... is there an efficient algorithm to solve this problem? ...i'd just like a clue

Not Yet Answered # another mouse and cheese problem... in a 2d field :P

VernonDozier 2,218 Salem 5,138 ArkM 1,090 Discussion Starter gregorynoob 2 Discussion Starter gregorynoob 2 Hi I'm having a problem implementing a mini shopping cart drop down in the header to show the user all the products they have in their shopping cart. It seems the only solution for this is Ajax, and I've looked all over and can't find anything that I could possibly ...

0

i tried going through a row while it's sum is higher than the column's and switching them that way but i kinda failed... is there an efficient algorithm to solve this problem? ...i'd just like a clue

0

It's C++ programming forum. Where is C++ in your post?..

There's no "Algorithm" or "Game Theory" section in Daniweb (as far as I know), so if gregorynoob is doing this in C++ and needs algorithm/strategy help, it seems like the right forum.

i tried going through a row while it's sum is higher than the column's and switching them that way but i kinda failed... is there an efficient algorithm to solve this problem? ...i'd just like a clue

I'd say you need three two-dimensional arrays. `cheese[a][b]`

represents the amount of cheese at square (a, b). `totalcheese[a][b]`

represents the amount of cheese eaten on the optimal path from (a,b) to (x,y). `direction[a][b]`

is the direction to take (up or right) from (a,b) if you are on the optimal path to (x,y). Optimal path will be the path where you eat the most cheese.

If `a == x`

, there is no calculation to be made. You must go up since going right takes you farther away from (x, y). Ditto when `b == y`

. You must go right for the same reason.

When a < x and b < y you need to compare `totalcheese[a+1][b]`

to `totalcheese[a][b+1]`

. Pick the greater and go that direction. In the event of a tie, pick either one. That means that `totalcheese[a+1][b]`

and `totalcheese[a][b+1]`

must be known before calculating `totalcheese[a][b]`

, so you'll be starting at (x,y) and moving away from it.

If you are moving up from (a,b), `totalcheese[a][b] = totalcheese[a][b+1] + cheese[a][b]`

.

That should be enough to get you started, I hope.

0

> i'd just like a clue

Draw a grid on some paper, and experiment with various strategies.

I always seem to get the same answer.

0

Excellently: now we have a forum where Salem (not gregorynoob) training his talents for algorithmes design...

Also we have empty slogan: "We only give homework help to those who show effort"...

0

well okay if this post has caused that much trouble for you ArkM, call a mod to remove it, i don't care really. And thanks for help to Vernon and Salem.

0

Ok, so i've found the possibly best solution to the problem using recursion with memoization... in case someone wants the code, here it is:

```
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAX 1000
int X, Y;
int map[ MAX ][ MAX ];
int memo[ MAX ][ MAX ];
int rec( int x, int y ) {
if( x < X-1 && y < Y-1 ) {
int r1 = 0, r2 = 0;
if( memo[x+1][y] )r1 = memo[x+1][y]; else r1 = rec( x+1, y );
if( memo[x][y+1] )r2 = memo[x][y+1]; else r2 = rec( x, y+1 );
memo[x][y] = std::max( map[x][y] + r1, map[x][y] + r2 );
return memo[x][y];
}
else if( x < X-1 ) {
int r1 = 0;
if( memo[x+1][y] )r1 = memo[x+1][y]; else r1 = rec( x+1, y );
memo[x][y] = ( map[x][y] + r1 );
return memo[x][y];
}
else if( y < Y-1 ) {
int r1 = 0;
if( memo[x][y+1] )r1 = memo[x][y+1]; else r1 = rec( x, y+1 );
memo[x][y] = ( map[x][y] + r1 );
return memo[x][y];
}
else return map[x][y];
}
int main( void )
{
memset( memo, 0, sizeof memo );
scanf( "%d%d", &X, &Y );
for( int i = 0; i < X; ++i )
for( int j = 0; j < Y; ++j )
scanf( "%d", &map[i][j] );
printf( "%d\n", rec( 0, 0 ) );
return 0;
}
```

and it doesn't use 3 matrixes...

this is an example of...top-down dynamic programming (i guess, think it's called that way in Sedgewick's book) so it recursively computes the largest amount that can be achieved on the way to the X, Y coordinate.

It uses another matrix to memoize the values so they don't have to be computed all over again!

This article has been dead for over six months. Start a new discussion instead.

Recommended Articles

Hello All ...

Iam Getting An Error With try to excecute the stored procedure .

I have Have Sql database , the stored procedure like so :

```
USE [MPRS]
GO
/****** Object: StoredProcedure [dbo].[Search_Licenses_By_Number] Script Date: 26-Nov-16 8:06:52 AM ******/
SET ANSI_NULLS ON
GO
SET QUOTED_IDENTIFIER ON
GO
ALTER PROCEDURE ...
```

Help! I want to create a java program that finds the highest even integer among the values entered by the user. Stop asking values when a value less than 1 have been entered. If no even integer is entered, display "No Even Integer"

Here is the sample output that I ...