My method is using DP, as Snehal have pointed out.
Suppose S[0..n-1] and T[0..n-1] denotes the score and time for the n
questions respectively.
C[k][s] denotes the maximum total time when choosing from the first k
questions such that the total score do not exceed s.
Then C[0][s] = 0
C[k][s] = max(C[k-1][s], C[k-1][s-S[k-1]]+T[k-1]), s>=S[k-1]
= C[k-1][s], s<S[k-1]
Suppose the total score/time of all problem is SS/ST and the passing
score is PS
then the answer is (TS - C[n][SS-PS]).
The time complexity is O(n*(SS-PS)).
Actually the 0/1 knapsack problem is a NP-complete problem, and only
have pseudo-polynomial time algorithm, or polynomial time greedy
approximation algorithm.
Refer to http://en.wikipedia.org/wiki/Knapsack_problem#0-1_knapsack_problem
On 2010-12-24 14:00, Ankur Khurana wrote:
how will you choose that ?? without sorting . can you please mention
what method you intend to use to achieve that purpose ?
On Fri, Dec 24, 2010 at 8:16 AM, Terence<[email protected]> wrote:
@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.
--
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.
