5. For the 0-1 Knapsack Problem, the item #1 has weight of 4 and the value...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
5. For the 0-1 Knapsack Problem, the item #1 has weight of 4 and the value of $12; the item #2 has weight of 1 and the value of $1; the item #3 has weight of 5 and the value of $10; and the item #4 has weight of 2 and the value of $8. The capacity of the knapsack's weight is 10. The Dynamic Programming algorithm has produced the following array. Fill the last two entries in the array and show how they are calcurated. 0 1 2 3 4 0 0 0 0 0 0 1 0 0 1 1 1 2 3 4 0 0 0 0 0 1 1 8 1 1 9 12 12 12 22 12 5 0 12 13 22 6 7 0 0 12 13 33 13 13 13 20 8 9 0 0 10 0 12 12 13 13 13 22 23 12 12 13 13 13 21 21 a) (6 pts) D[4][9] = b) (6 pts) D[4][10] = c) (8 pts) Which items should be put in the knapscak to achieve the maximum profit? Show how you determined this result. 5. For the 0-1 Knapsack Problem, the item #1 has weight of 4 and the value of $12; the item #2 has weight of 1 and the value of $1; the item #3 has weight of 5 and the value of $10; and the item #4 has weight of 2 and the value of $8. The capacity of the knapsack's weight is 10. The Dynamic Programming algorithm has produced the following array. Fill the last two entries in the array and show how they are calcurated. 0 1 2 3 4 0 0 0 0 0 0 1 0 0 1 1 1 2 3 4 0 0 0 0 0 1 1 8 1 1 9 12 12 12 22 12 5 0 12 13 22 6 7 0 0 12 13 33 13 13 13 20 8 9 0 0 10 0 12 12 13 13 13 22 23 12 12 13 13 13 21 21 a) (6 pts) D[4][9] = b) (6 pts) D[4][10] = c) (8 pts) Which items should be put in the knapscak to achieve the maximum profit? Show how you determined this result.
Expert Answer:
Answer rating: 100% (QA)
1main code A dynamic programming based solution for 01 Knapsack problem inclu... View the full answer
Related Book For
College Algebra
ISBN: 978-0134697024
12th edition
Authors: Margaret L. Lial, John Hornsby, David I. Schneider, Callie Daniels
Posted Date:
Students also viewed these programming questions
-
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...
-
The following additional information is available for the Dr. Ivan and Irene Incisor family from Chapters 1-4. Ivan and Irene paid the following in 2012 (all by check or can otherwise be...
-
8 D D D D P P P P P P P P P P P 10 Functions What is defusion. What is osnosis What is Tornicity The power house of the cell functions of the plasma? What is facilitated defusion? do they need ATP?...
-
A swimming pool is 20 ft wide, 40 ft long, 3 ft deep at the shallow end, and 9 ft deep at its deepest point. A cross-section is shown in the figure. If the pool is being filled at a rate of...
-
If P (B) = 0.30, P (A B) = 0.60, P (B) = 0.70, and P (A B) = 0.50, find P (B A)
-
Match the measures of worth in the first column with one (or more) of the analysis approaches that is (are) appropriate for that measure. Measure of Worth (a) Annual Worth (b) External Rate of Return...
-
Depletion and DepreciationMining Khamsah Mining Company has purchased a tract of mineral land for $900,000. It is estimated that this tract will yield 120,000 tons of ore with sufficient mineral...
-
Income elasticity Ei for food is about 0.30. Last year Ali spent $12,000 on food. If he gets a 4% raise in annual pay how much will he spent on food next year?
-
Given the following demand functions, express TR as a function of Q and hence sketch the graphs of TR against Q: (a) P = 4 (b) P = 7/Q (c) P = 10 4Q
-
3.(6) Calculate the activation energy, Ea, in kJ/mol for the following reaction from the observed rate constants K25c = 3.46 X 105 s and kssc= 1.50 X 10 s. 2N2Os(g) 4NO2(g) + O2(g)
-
An individual can build up his or her capital ______. a) by working longer hours only b) by cutting back on consumption only c) by both cutting back on consumption and working longer hours d) by...
-
Where is a price ceiling with respect to equilibrium price? What will be the relative size of quantity demanded and quantity supplied?
-
Which statement is the most accurate? a) Most of the worlds economies are close copies of the American capitalist model. b) The Chinese economy can best be described as democratic socialist. c)...
-
Capital comes from ______. a) gold b) savings c) high consumption d) the government
-
Which statement is the most accurate? a) During the 1980s, people in the Soviet Union and China who worked their own private plots were much more productive than those working on large collective...
-
Perotiga Bhd is a company involved in the automotive industry located in Southern Malaysia since 1998. Perotiga Bhd plans to expand its business by having another factory building in Northern...
-
CLASS PERIO Solving Linear Equations: Variable on Both Sides Solve each equation. 1) 6r+ 7 = 13 + 7r 3) -7x-3x+2=-8x-8 5)-14 +66+7-26=1+5b 7) n-3n = 14-4n 2) 13-4x=1-x 4)-8-x= x - 4x 6)n+2=-14-n 8)...
-
Decide what values of the variable cannot possibly be solutions for each equation. Do not solve. 5/2x + 3 - 1/x - 6 = 0
-
Solve each system for x and y using Cramers rule. Assume a and b are nonzero constants. + by
-
Solve the equation. 4x - 2 = 3x + 1
-
Mega Tech, Inc. designs and manufactures automotive components. For years, the company enjoyed a stable marketplace, a small but loyal group of customers, and a relatively predictable environment....
-
Describe the features of a project. How do they differ from day-to-day processes within an organization?
-
In 2003, the Department of Health and Human Services in Victoria, Australia, initiated a AU$323 million project to develop HealthSMART, an integrated IT system that would deliver resource management,...
Study smarter with the SolutionInn App