Agilent Technologies Interview Question Software Engineer / Developers
Q_i is max number of questions of type i.
M_i is marks for question of type i.
T_i is the time require from question of type i.
Cutoff is C.
If we select q_i questions of type i, we need to
Minimize q_i*T_i
subject to
q_i <= Q_i
Sum q_i*M_i >= C
This is bounded knapsack, is NP-Hard (not again... boo hoo) and is solvable by dynamic programming in pseudo polynomial time.
@above
Thanks for the reply.
It would be easier for me to modulize this problem into knapsack, if we have only two arrays(Q_i == 1 {for 0<=i<=n), but since Q_i >=1, we have 3 different arrays.
Should we consider Knapsack weight array = {q_i*M_i for all summation(Q_i) combinations}
And the knapsack value array = { q_i*T_i for all summation(Q_i) combinations}
But then the knapsack weight and value arrays, will contain duplicate values for all the q_i in Q_i.
Can u please, help me out in moduling the same.
Don't understand what you are asking. Check the web though. Wiki page might have something.
I wants to ask, how can i refine this problem into bounded knapsack problem, as a knapsack problem has only two array, Weight Array and Value Array. But in this case we have one more array.
Continue:
- Learner August 18, 2011For e.g an input could be:
Question[] -> 5 , 2 , 4 , 6 , 3, 1
Marks[]-> 8, 3, 2, 1, 6, 10
Time[]-> 2, 1, 3, 5, 4, 6