@Ankur:
It is just 0/1 knapsack problem:
Choose a subset of the questions with sum of scores not exceeding
(Total Score - Pass Score), while maximize the sum of time of the subset.
So I do not think O(nlogn) greedy algorithm will solve this problem.
On 2010-12-23 23:38, Ankur Khurana wrote:
it is just like 0/1 knapsack problem with maximum weight of knapsack
as 40. but in this case that is minimum that we have to calculate.
calculate marks/time for every element . then try finding the elements
with max value/time to fulfill the quota of marks. i dont know if this
can be done in O(n) but it can be certainly done in nlogn. any other
views ?
On Thu, Dec 23, 2010 at 9:03 PM, Davin<[email protected]> wrote:
Thanks for reply. I am looking for O(n) for solution.
Davin
On Dec 23, 8:29 pm, snehal jain<[email protected]> wrote:
hint : use dp
On Thu, Dec 23, 2010 at 8:30 PM, Davin<[email protected]> wrote:
Marks for Questions(1,6): {10,15,20,25,10,20}
Time for Each Questions(1,6) : { 2, 4,3,4, 2,4}
Passing Marks : 40 Out of 100
Find Questions with minimum time to pass the exam?
On Dec 23, 7:04 pm, juver++<[email protected]> wrote:
Please clarify the problem statement. Provide example.
From the first view problem seems to be unclear.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected]<algogeeks%2bunsubscr...@googlegroups
.com>
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups "Algorithm
Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups "Algorithm
Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
