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
-
9 The company has identified the following information about its overhead activity pools and the two product lines: Activity Pools Materials handling Quality control Machine maintenance Required:...
-
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?...
-
During the year ended December 31, 2012, McCormick Inc. had the following transactions for its trading investments: Jan. 1 Purchased 2,000 Starr Corporation $5, preferred shares for $210,000 cash....
-
Research in the area of HR of Nestle and Provide a brief overview of the company and its HR department Include a copy of the company's mission and vision. Describe in detail HR-related issues or...
-
What can happen when an executive committee has too much power and autonomy?
-
The Clarkson Company recently reported net profits after taxes of $15.8 million. It has 2.5 mil-lion shares of common stock outstanding and pays preferred dividends of $1 million a year. The companys...
-
You have been hired as a consultant for Pristine Urban - Tech Zither, Inc. ( PUTZ ) , manufacturers of fine zithers. The market for zithers is growing quickly. The company bought some land three...
-
Last August, Malcolm (who is single) moved out of his rented apartment in Toronto, Ontario, to move to Vancouver, British Columbia, where he now lives and works. Malcolm has two T4s, one from Ontario...
-
Option 2: Using OrCAD create a new PSpice analog project. Construct a R-L voltage divider circuit using a 1k2 resistor and 10 mH inductor (code 103) as shown on the previous page (instructions for...
-
Define a compound machine.
-
Define vacuum efficiency and condenser efficiency.
-
Differentiate between load and effort.
-
What are the effects of air infiltration in condensers ?
-
What is a reversible machine ?
-
Which of the required readings from "Reflections of Canada" did you find most interesting and why? Did it confirm or challenge your perspective on a major issue? If so, what issue and in what way did...
-
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
-
Describe and explain the difference between the short run and the long run.
-
Which of the following is true? a. Productive efficiency occurs in perfect competition because the firm produces at the minimum of the ATC curve. b. Allocative efficiency occurs when P = MC;...
-
Describe and explain the concept of economic profits and sunk costs.
Study smarter with the SolutionInn App