Need an algorithm

Master · Post by **Master** » Mon Oct 04, 2004 2:34 pm

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

Eduard · Post by **Eduard** » Mon Oct 04, 2004 7:58 pm

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.

anupam · Post by **anupam** » Mon Oct 04, 2004 9:38 pm

Use DP for 10690 and 10664.

Master · Post by **Master** » Tue Oct 05, 2004 3:21 pm

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

Adrian Kuegel · Post by **Adrian Kuegel** » Tue Oct 05, 2004 6:31 pm

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.