Page 1 of 1
Need an algorithm
Posted: Mon Oct 04, 2004 2:34 pm
by Master
There are some problem where we have to find out two sequence of numbers from a given sequence with some given criteria. Such as problem 10690 or 10705. Can anyone tell me about this type of algorithm.
Pls don
Posted: Mon Oct 04, 2004 7:58 pm
by Eduard
Hello Master.
I think problem 10690 and 10705 are not similiar problems.Problem 10690 is much more similiar to problem 10664.And 10664 is well known problem (wich you can solve even with Backtreking).If you can solve 10664 without backtrecking with another algo than you can solve 10690(algorithms are very similiar).
The problem 10705 is another kind of problem,and have some solutions.
I know that there is a greedy solution but mine is not greedy.
If you want I can give you my algorithm for this problem.
Eduard.
Posted: Mon Oct 04, 2004 9:38 pm
by anupam
Use DP for 10690 and 10664.
Posted: Tue Oct 05, 2004 3:21 pm
by Master
Thanks Eduard and Anupam
I want the DP solution. I don't know how can i do it
. Would u pls give me the algorithm.
Pls Don't refer any books.
Thanks
M H Rasel
CUET Old Sailor
Posted: Tue Oct 05, 2004 6:31 pm
by Adrian Kuegel
Well, in this case I can also refer to internet. The dp algorithm needed is the one for the knapsack problem, this is a very well known problem where you can find lots of information in the internet (just search for 0/1 knapsack problem dynamic programming)
Here is a link I found:
http://www-cse.uta.edu/~holder/courses/ ... ode12.html
For the mentioned problems, just use weight = 1 for all objects.