neutrino86 Posted October 18, 2005 Share Posted October 18, 2005 I have no clue on how to do this, besides the use of a brute force algo. Given a single aircraft to start with, an airline company decides to start a contract based rent-a-plane business... Given the starting and ending time of the contract offered by the would be passengers, and the cost they are willing to bear, develop an algorithm to decide which contracts to take, keeping in mind, that the highest amount of profit is to be developed. The contracts can be contiguous in their periods. The number of contracts which can be given as input can be upto 100000 in number. So time is a constraint with the algorithm. Please share your ideas. Link to comment Share on other sites More sharing options...
neutrino86 Posted October 23, 2005 Author Share Posted October 23, 2005 umm....In case any of you missed this thread...Here it is again... Given a single aircraft to start with, an airline company decides to start a contract based rent-a-plane business... Given the starting and ending time of the contract offered by the would be passengers, and the cost they are willing to bear, develop an algorithm to decide which contracts to take, keeping in mind, that the highest amount of profit is to be developed. The contracts can be contiguous in their periods. The number of contracts which can be given as input can be upto 100000 in number. So time is a constraint with the algorithm. please share your ideas... Link to comment Share on other sites More sharing options...
lwebzem Posted October 23, 2005 Share Posted October 23, 2005 I would first build the graph for all possible contacts and then apply dynamic programming. Here is the first step: Input data in the form for each contract ordered by starttime START_TIME END_TIME COST id N number of contracts FOR i=1 TO N END_NODE= True MIN_END_TIME=99999 FOR j=i+1 TO N IF MIN_END_TIME <= START_TIME(j) THEN EXIT FOR 'we are done for node i ELSE IF END_TIME(j) < MIN_END_TIME THEN MIN_END_TIME=END_TIME(j) END IF END IF IF START_TIME(j) >= END_TIME(i) THEN W(i,j)=Cost(i) END_Node=False END IF NEXT IF END_Node=True then ' I am adding the end node so ' all paths will be finished in this node W(i,N+1)=0 END IF NEXT ' Now adding the start node FOR i=1 to N W(0,i)=Cost(i) NEXT ' So the weight for link from START node to node 1 is the cost of contract 1 ' the weight for link from node 4 to node 5 is the cost of contract 5 and so on.... Now I believe we can apply the dynamic programming to find path from START node to END node with max sum of weight whict will be prophit or cost from contracts. It will be similar to finding shortest path algorithm. Link to comment Share on other sites More sharing options...
neutrino86 Posted October 25, 2005 Author Share Posted October 25, 2005 hmmm...i'll think about it a bit... i am not in friends with dynamic programming right now. Thankyou for your effort. Link to comment Share on other sites More sharing options...
Recommended Posts
Create an account or sign in to comment
You need to be a member in order to leave a comment
Create an account
Sign up for a new account in our community. It's easy!
Register a new accountSign in
Already have an account? Sign in here.
Sign In Now