Given items as {value,weight} pairs {{40,20},{30,10},{20,5}}. The capacity of knapsack=20. Find the maximum value output assuming items to be divisible. Options 40 80 100 None of the mentioned
Question
Given items as {value,weight} pairs {{40,20},{30,10},{20,5}}. The capacity of knapsack=20. Find the maximum value output assuming items to be divisible.
Options 40
80
100
None of the mentioned
Solution
This problem can be solved using the concept of Greedy Algorithms. Here are the steps:
-
First, calculate the value per unit weight for each item. For the given items, the values per unit weight are {2,3,4} respectively.
-
Sort the items based on the value per unit weight in descending order. So, the sorted items are {{20,5},{30,10},{40,20}}.
-
Start filling the knapsack with the item that has the highest value per unit weight. Continue this process until the knapsack is full or there are no more items.
-
If the knapsack is full before all items are included, then include the fraction of the next item that will completely fill the knapsack.
Let's calculate:
-
The first item {20,5} can be completely included in the knapsack. So, the total value is 20 and the remaining capacity of the knapsack is 15.
-
The second item {30,10} can also be completely included in the knapsack. So, the total value is now 50 and the remaining capacity of the knapsack is 5.
-
The third item {40,20} cannot be completely included in the knapsack because its weight is more than the remaining capacity of the knapsack. So, we include the fraction of it that will completely fill the knapsack. The fraction is 5/20 = 0.25. So, the value of the included fraction is 0.25 * 40 = 10.
So, the maximum value that can be obtained is 20 + 30 + 10 = 60.
Therefore, none of the mentioned options is correct.
Similar Questions
ou are given a knapsack that can carry a maximum weight of 60. There are 4 items with weights {20, 30, 40, 70} and values {70, 80, 90, 200}. What is the maximum value of the items you can carry using the knapsack?
Given weights and values of N items, we need to put these items in a knapsack of capacity W to get the maximum total value in the knapsack.Note: Unlike 0/1 knapsack, you are allowed to break the item here.
Question1Max. score: 100.000/1 Knapsack ProblemYou are given weights and values of N items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack. Note that we have only one quantity of each item.In other words, given two integer arrays val[0..N-1] and wt[0..N-1] which represent values and weights associated with N items respectively. Also given an integer W which represents knapsack capacity, find out the maximum value subset of val[] such that sum of the weights of this subset is smaller than or equal to W. You cannot break an item, either pick the complete item, or don’t pick it (0-1 property).Input:First Line Containf the size of the itemsSecond line contains Profit valuesThird Line Contains Weights Fourth line contains Capacity Output: Output=Max ProfitExample 1:Input:31 2 34 5 1 3Output: 3
Solve the following instance of greedy knapsack problem where n=4, m=10, p = (40, 42, 25,12) and w = (4, 7, 5, 3)
Which of the following problems is equivalent to the 0-1 Knapsack problem?a.You are given a bag that can carry a maximum weight of W. You are given N items which have a weight of {w1, w2, w3,…., wn} and a value of {v1, v2, v3,…., vn}. You can break the items into smaller pieces. Choose the items in such a way that you get the maximum valueb.You are studying for an exam and you have to study N questions. The questions take {t1, t2, t3,…., tn} time(in hours) and carry {m1, m2, m3,…., mn} marks. You can study for a maximum of T hours. You can either study a question or leave it. Choose the questions in such a way that your score is maximizedc.You are given a suitcase that can carry a maximum weight of 15kg. You are given 4 items which have a weight of {10, 20, 15,40} and a value of {1, 2, 3,4}. You can break the items into smaller pieces. Choose the items in such a way that you get the maximum valued.You are given infinite coins of denominations {v1, v2, v3,….., vn} and a sum S. You have to find the minimum number of coins required to get the sum S
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.