The problem in which we break the item is known as a Fractional knapsack problem. In fractional knapsack, the items are broken in order to maximize the profit. Obeying a greedy strategy, the thief begins by taking as much as possible of the item with the greatest value per pound. The fractional knapsack problem is also one of the techniques which are used to solve the knapsack problem. To solve the fractional problem, we first compute the value per pound v_i = b_i / w_i for each item i. As the Fig 16.2 in CRLS demonstrates, although the problems are similar, we can solve the fractional knapsack problem by a greedy strategy, but we cannot solve the 0-1 problem by such a strategy.» Design and Analysis of Algorithms solved MCQs.
#FRACTIONAL KNAPSACK PLUS#
consider that if we remove a weight w of one item j from the optimal load, the remaining load must be the most valuable load weighing at most W - w that the thief can take from the n-1 original items plus w_j - w pounds of item j (the remains of item j). Explanation: fractional knapsack problem is also called continuous knapsack problem.If we remove item j from this load, the remaining load must be the most valuable load weighing at most W - w_j that the thief can take from the n-1 original items excluding item j.For the 0-1 problem, consider the most valuable load that weighs at most W pounds.You can think of an item in the 0-1 knapsack problem as being like a gold ingot and an item in the fractional knapsack problem as more like gold dust.īoth knapsack problems exhibit the optimal-substructure property. In this setting, the thief can take fractions of items, rather than having to make a binary (0-1) choice for each item.
0 kommentar(er)
