Given items as {value,weight} pairs {{60,20},{50,25},{20,5}}. The capacity of knapsack=40. Find the maximum value output assuming items to be divisible and nondivisible respectively.(a) 100, 80(b) 110, 70(c) 130, 110(d) 110, 80I got this question in an online quiz.Question is taken from Greedy Algorithms in portion Greedy Algorithms of Data Structures & Algorithms II

Given items as {value,weight} pairs {{60,20},{50,25},{20,5}}. The capa

1.	Given items as {value,weight} pairs {{60,20},{50,25},{20,5}}. The capacity of knapsack=40. Find the maximum value output assuming items to be divisible and nondivisible respectively.(a) 100, 80(b) 110, 70(c) 130, 110(d) 110, 80I got this question in an online quiz.Question is taken from Greedy Algorithms in portion Greedy Algorithms of Data Structures & Algorithms II
Answer» CORRECT OPTION is (d) 110, 80 The best I can EXPLAIN: Assuming items to be divisible- The value/weight ratio are {3, 2, 4}.So we include third and first items wholly. So, now only 15 units of volume are left for SECOND item. So we include it partially. Final volume = 20+60+50x(15/25)=80+30=110 Assuming items to be indivisible- In this case we will have to leave ONE item due to insufficient capacity. Final volume = 60 + 20 = 80.

Discussion

No Comment Found

Related InterviewSolutions

How many printable characters does the ASCII character set consists of?(a) 120(b) 128(c) 100(d) 98I have been asked this question in an interview for internship.The doubt is from Greedy Algorithms topic in chapter Greedy Algorithms of Data Structures & Algorithms II
What is the running time of the Huffman algorithm, if its implementation of the priority queue is done using linked lists?(a) O(C)(b) O(log C)(c) O(C log C)(d) O(C^2)The question was posed to me in a national level competition.This intriguing question originated from Greedy Algorithms in division Greedy Algorithms of Data Structures & Algorithms II
What is the running time of the Huffman encoding algorithm?(a) O(C)(b) O(log C)(c) O(C log C)(d) O( N log C)This question was addressed to me during a job interview.This intriguing question originated from Greedy Algorithms in chapter Greedy Algorithms of Data Structures & Algorithms II
The type of encoding where no character code is the prefix of another character code is called?(a) optimal encoding(b) prefix encoding(c) frequency encoding(d) trie encodingThis question was posed to me in a job interview.My query is from Greedy Algorithms topic in section Greedy Algorithms of Data Structures & Algorithms II
An optimal code will always be present in a full tree.(a) true(b) falseI had been asked this question at a job interview.The origin of the question is Greedy Algorithms in division Greedy Algorithms of Data Structures & Algorithms II
What will be the cost of the code if character ci is at depth di and occurs at frequency fi?(a) cifi(b) ∫cifi(c) ∑fidi(d) fidiThe question was asked during an interview.The query is from Greedy Algorithms topic in chapter Greedy Algorithms of Data Structures & Algorithms II
From the following given tree, what is the computed codeword for ‘c’?(a) 111(b) 101(c) 110(d) 011I got this question in an interview for job.This intriguing question comes from Greedy Algorithms in division Greedy Algorithms of Data Structures & Algorithms II
From the following given tree, what is the code word for the character ‘a’?(a) 011(b) 010(c) 100(d) 101This question was posed to me in exam.This intriguing question originated from Greedy Algorithms topic in chapter Greedy Algorithms of Data Structures & Algorithms II
The code length does not depend on the frequency of occurrence of characters.(a) true(b) falseI got this question in final exam.The question is from Greedy Algorithms in section Greedy Algorithms of Data Structures & Algorithms II
In Huffman coding, data in a tree always occur?(a) roots(b) leaves(c) left sub trees(d) right sub treesThis question was posed to me in semester exam.The origin of the question is Greedy Algorithms in chapter Greedy Algorithms of Data Structures & Algorithms II

Discussion

No Comment Found

Related InterviewSolutions

Reply to Comment