Need an algorithm

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
Master
Learning poster
Posts: 82
Joined: Thu Oct 10, 2002 1:15 pm
Location: St. Johns, Canada
Contact:

Need an algorithm

Post 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

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

Post 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.
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam »

Use DP for 10690 and 10664.
"Everything should be made simple, but not always simpler"

Master
Learning poster
Posts: 82
Joined: Thu Oct 10, 2002 1:15 pm
Location: St. Johns, Canada
Contact:

Post by Master »

Thanks Eduard and Anupam

I want the DP solution. I don't know how can i do it :roll: . Would u pls give me the algorithm.

Pls Don't refer any books.

Thanks
M H Rasel
CUET Old Sailor

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post 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.

Post Reply

Return to “Algorithms”