Suggest the algorithm.
Note:- I am NOT asking you to write the program for me. I am NOT asking you to do the homework for me either. All I am asking you is if you could suggest an algorithm for me.
Present below are two algorithms. Can you please suggest me an algorithm to make the c++ program for them.Thanks in advance.
Problem 1 : Grid game
You are given a square grid of positive and negative numbers. You have to start at the top left corner of the grid and find a path to the bottom-right corner. In each step, you are only allowed to move one position to the right or one position down. As a special bonus, you are allowed at most one move that can be either to the left or up. Note that you are allowed to visit a position more than once as a result of this special move.
Your aim is to find such a path that has the maximum weight, where the weight of a path is the sum of all the numbers visited along the path.
Input format
The first line of the input contains one integer N, the number of rows and columns in the grid. Lines 2 to N+1 describe the N rows of the grid. Each of these N lines of input consists of N space separated integers, corresponding to the numbers in one row.
Notes
In all cases, N ≤ 2000. Each number in the grid is guaranteed to be less than 1000.
Sample Input
4
12 -16 10 -12
-16 13 -14 7
7 -4 16 -15
-7 16 -9 8
[B]
--------------------------------------
Problem 2 : Choosing chocolates
Santa Claus has lined up a row of bowls, each containing some chocolates. Nikhil has been told that he can pick up as many of these bowls as he wants, provided that he never picks two consecutive bowls.
Your aim is to help Nikhil choose a set of bowls so that he maximizes the number of chocolates that he picks up.
Input format
The first line of the input contains one integer N, the number of bowls. This is followed by a line containing N integers, describing the number of chocolates in each of the N bowls.
Notes
In all cases, N ≤ 100,000.
Sample Input
10
30 10 8 20 11 12 25 13 20 19
Present below are two algorithms. Can you please suggest me an algorithm to make the c++ program for them.Thanks in advance.
Problem 1 : Grid game
You are given a square grid of positive and negative numbers. You have to start at the top left corner of the grid and find a path to the bottom-right corner. In each step, you are only allowed to move one position to the right or one position down. As a special bonus, you are allowed at most one move that can be either to the left or up. Note that you are allowed to visit a position more than once as a result of this special move.
Your aim is to find such a path that has the maximum weight, where the weight of a path is the sum of all the numbers visited along the path.
Input format
The first line of the input contains one integer N, the number of rows and columns in the grid. Lines 2 to N+1 describe the N rows of the grid. Each of these N lines of input consists of N space separated integers, corresponding to the numbers in one row.
Notes
In all cases, N ≤ 2000. Each number in the grid is guaranteed to be less than 1000.
Sample Input
4
12 -16 10 -12
-16 13 -14 7
7 -4 16 -15
-7 16 -9 8
[B]
--------------------------------------
Problem 2 : Choosing chocolates
Santa Claus has lined up a row of bowls, each containing some chocolates. Nikhil has been told that he can pick up as many of these bowls as he wants, provided that he never picks two consecutive bowls.
Your aim is to help Nikhil choose a set of bowls so that he maximizes the number of chocolates that he picks up.
Input format
The first line of the input contains one integer N, the number of bowls. This is followed by a line containing N integers, describing the number of chocolates in each of the N bowls.
Notes
In all cases, N ≤ 100,000.
Sample Input
10
30 10 8 20 11 12 25 13 20 19
I think both problems can be solved with backtracking
http://en.wikipedia.org/wiki/Backtracking
With this algorithm in recursive functions you can chek every possible way and with comparing the results you'll get the highest.
http://en.wikipedia.org/wiki/Backtracking
With this algorithm in recursive functions you can chek every possible way and with comparing the results you'll get the highest.
Yeah, backtracking seems like a good idea, (...unless it is explicitly forbidden).
If you have access to some bibliography, check Brassard & Bratley's "Fundamentals of Algorithmics". The backtracking section should be marked somewhere in the index, so check it out.
If you have access to some bibliography, check Brassard & Bratley's "Fundamentals of Algorithmics". The backtracking section should be marked somewhere in the index, so check it out.
Last edited on
Thank you guys for your replies. I'll sure check it out.
Though the wiki article doesnt explain quite much.
Though the wiki article doesnt explain quite much.
These are examples of dynamic algorithm. Basically dynamic algorithm is backtracking with memory, i.e. if you know that one of the partial solution is always better than the other partial solution, dont consider the first one further.
e.g. in first case we know that path -12,10,-14 is better that -12,7,-14. So there is no need to consider -12,7,-14,-15.
in second we know that if we include 30 and 25, then the best set is 30 20 25, then no need to consider 30 8 11 25 20.
The classical example is matrix chain multiplication.
http://en.wikipedia.org/wiki/Matrix_chain_multiplication
e.g. in first case we know that path -12,10,-14 is better that -12,7,-14. So there is no need to consider -12,7,-14,-15.
in second we know that if we include 30 and 25, then the best set is 30 20 25, then no need to consider 30 8 11 25 20.
The classical example is matrix chain multiplication.
http://en.wikipedia.org/wiki/Matrix_chain_multiplication
Dynamic programming sounds like a good idea, but only if you've already done some backtracking exercises before. Also, Dynamic Programming is NOT backtracking with memory. Only problems that verify Bell's optimality principle can be solved through this technique.
Nikhar if you feel adventurous enough, you can give a try to this technique, but it's more difficult than backtracking.
Nikhar if you feel adventurous enough, you can give a try to this technique, but it's more difficult than backtracking.
Hey guys......Thanks everyone for the reply. But I'm not at all familiar with backtracking. Can anyone suggest me a few backtracking exercises? A site with backtracking examples.
Topic archived. No new replies allowed.