Consider the following knapsack problem with W = 13: Vi Wi 5 5 4 6 7...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
Consider the following knapsack problem with W = 13: Vi Wi 5 5 4 6 7 8 7 4 (a) Thinking of the above problem as a fractional knapsack problem and using the optimal greedy approach, give the best possible fractional knapsack problem solution. (b) Considering the same problem but this time as an integer knapsack problem. Make a branch and bound graph as was done in the lectures. Highlight the optimal solution. (c) Let's modify the above problem to the 0-1 integer knapsack problem where you can either take a full item or leave a full item and you only have at most one of any item (in other words, this is the integer knapsack problem where each c; is either 0 or 1). Use the same greedy approach from the previous problem to find a solution. Does this give the optimal solution? Justify your answer by drawing a full backtracking tree of all possibilities. Consider the following knapsack problem with W = 13: Vi Wi 5 5 4 6 7 8 7 4 (a) Thinking of the above problem as a fractional knapsack problem and using the optimal greedy approach, give the best possible fractional knapsack problem solution. (b) Considering the same problem but this time as an integer knapsack problem. Make a branch and bound graph as was done in the lectures. Highlight the optimal solution. (c) Let's modify the above problem to the 0-1 integer knapsack problem where you can either take a full item or leave a full item and you only have at most one of any item (in other words, this is the integer knapsack problem where each c; is either 0 or 1). Use the same greedy approach from the previous problem to find a solution. Does this give the optimal solution? Justify your answer by drawing a full backtracking tree of all possibilities.
Expert Answer:
Answer rating: 100% (QA)
a In the fractional knapsack problem the optimal greedy approach is to sort items by valuetowei... View the full answer
Related Book For
Income Tax Fundamentals 2013
ISBN: 9781285586618
31st Edition
Authors: Gerald E. Whittenburg, Martha Altus Buller, Steven L Gill
Posted Date:
Students also viewed these programming questions
-
Planning is one of the most important management functions in any business. A front office managers first step in planning should involve determine the departments goals. Planning also includes...
-
The following additional information is available for the Dr. Ivan and Irene Incisor family from Chapters 1-5. Ivan's grandfather died and left a portfolio of municipal bonds. In 2012, they pay Ivan...
-
In a two-player, one-shot simultaneous-move game each player can choose strategy A or strategy B. If both players choose strategy A, each earns a payoff of $500. If both players choose strategy B,...
-
Foxey Distributors had the following transactions for the month of April 2017: Apr. 1 Sold $3,000 of merchandise to James Moss, terms n/30. Inventory had a cost of $1,340. The sale was subject to 7...
-
Give an example of component lifestyles based on someone you know?
-
Critical pressure ratio for the flow of gases through a converging nozzle is given by (a) \(\left(\frac{2}{\gamma+1} ight)^{\gamma / \gamma-1}\) (b) \(\left(\frac{1}{\gamma+1} ight)^{\gamma /...
-
Exact Photo Service purchased a new color printer at the beginning of 2016 for $38,000. The printer is expected to have a four-year useful life and a $3,500 salvage value . The expected print...
-
S The four people below have the following investments. Invested Amount Interest Rate Jerry Elaine $ 11,800 12% 14,800 8 Compounding Quarterly Semiannually 21,800 7 17,800 9 Annually Annually George...
-
Say-on-pay votes by shareholders are now quite common. Occasionally, shareholders' non-binding votes do not approve executive compensation. For example, in 2013, share holders of Barrick Gold Corp....
-
The stress in foam core with metal cover plates is O O = - MY /I Y/I -Y/I Y/I
-
How long does it take for a deposit of $500 to double at 10% compounded continuously? How many years does it take to double? years days
-
You are getting ready to start a new project that will incur some cleanup and shutdown costs when it is completed. The project costs $ 5.35 million up front and is expected to generate $ 1.19 million...
-
/ 1- be f(x)? If - 2 dx = sin (x) - f(x)+C, which could
-
Evaluate the following 2 A [ (x 1) e + + x dr
-
Estimate the limit x-1 lim x-0+ ln x + x-1
-
Problem #5 Consider the statements P and Q P-Kayla (she/her) goes sailing Q-Kayla has paid the docking fee this month A. For each English statement below, list ALL truth values for P and Q that would...
-
Which one of the following anhydrous chloride is not obtained on direct heating of its hydrated chloride? (A) BaCl2 (B) CaClz (C) MgCl2 (D) SrCl2
-
John Fuji (age 37) moved from California to Washington in December 2011. He lives at 468 Cameo Street, Yakima, WA 98901. John's Social Security number is 571-78-5974 and he is single. His earnings...
-
Mike purchases a heavy-duty truck (5-year class recovery property) for his delivery service on April 30, 2012. The truck is not considered a passenger automobile for purposes of the listed property...
-
William sold Section 1245 property for $25,000 in 2012. The property cost $35,000 when it was purchased 5 years ago. The depreciation claimed on the property was $16,000. a. Calculate the adjusted...
-
Using only the linear part of the moisture absorption curve for a temperature of \(77^{\circ} \mathrm{C}\) in Figure 5.12, and assuming a thickness of \(2.54 \mathrm{~mm}\), estimate the diffusivity...
-
The filament-wound E-glass/epoxy pressure vessel described in Example 4.4 is to be used in a hot-wet environment with temperature \(T=100^{\circ} \mathrm{F}\) \(\left(38^{\circ} \mathrm{C} ight)\)...
-
For the composite properties and environmental conditions described in Examples 3.6, 4.7, and 5.3, determine the hygrothermally degraded values of the longitudinal and transverse tensile strengths....
Study smarter with the SolutionInn App