Answered: knapsack problem: given the first…

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Question

knapsack problem:

given the first table: c beeing value and w beeing weight, W max weight. I got table 2 as a solution to:

2 Solve the Knapsack problem with dynamic programming. To do this, enter the numbers Opt[k,V ] for k = 1,...,5 and V = 1,...,9 in a table. Here Opt[k, V ] is the partial solution obtained for the first k items with maximum weight V. "

Can somebody explain me the values of the table? How do they get calculated?

Also how do i solve the followup-task:

Using the values in the table, determine a solution OPTSOL(I)=(β1,β2,β3,β4), starting with β4. (Use backtracing to do this)

W
8
3
5 6
21
000 29 2: 21 21 21
21
2
1012
78
9
24 24 24
69858.
21 140 90 64 64 85 85
100 21 21 21 21
200 21
0 21 21
21 64 64
64
30621
621 21 40 40 69 64 85 85
40 021 38 40 59 64 78 85 102
46
69
50
6 21 38 40 63 64 84 101 103

C1
21
C2 C3 C4
C5
64 19 38 63
W1
W2 W3
W4 W5
2 6 2 35
W
9

Expert Solution

Step by step

Solved in 2 steps

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Similar questions