Question

Solve the following instance of the 0/1 knapsack problem by using dynamic programming approach. Where W=5...

Solve the following instance of the 0/1 knapsack problem by using dynamic programming approach. Where W=5

item

weight

Value

1

3

SR 40

2

2

SR 6

3

1

SR 20

4

4

SR 12
Engineering   Computer-Science   
0 0
Add a commentTranscribed image text
Next >

Homework Answers

Answer #1
Weight 3 2 1 4
Profit 40 6 20 12
item no 1 2 3 4
DP solu. 1 0 1 0

Note1: Comparing all leaf nodes possibility ,solution according to dynamic programming is (1,0,1,0)

(0,0) (12,4) (20,1) (32,5) (6,2) (18,6) (26,3) (38,7) (40,3) (52,7) (60,4) (72,8) (46,5) (58,9) (66,6) (78,10)

// Red mark are invalid bez w=5

(0,0) (12,4) (20,1) (32,5) (6,2) (26,3) (40,3) (60,4) (46,5)

// among this  (60,4) is giving solution according to dynamic programming.

Note2: we can solve this by table method also but in this way(tree) we can explore dynamic programming more efficiently.

0 0
Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
the table is for 0-1 knapsack problem given for the following items, each labeled with weight...
the table is for 0-1 knapsack problem given for the following items, each labeled with weight and value. Assume the total weight limit W is 8 lbs. Item 1 2 3 4 Value ($) 8 40 30 54 Weight (lb) 1 2 3 6 Solve the fractional knapsack problem using the input?
KNAPSACK Optimization Problem using Greedy Method Problem 1: Item Weight Value 1    14 20 2...
KNAPSACK Optimization Problem using Greedy Method Problem 1: Item Weight Value 1    14 20 2     6 16 3   10 8 4     5 10 5   4 12 Allowed weight = 24 Kg Problem 2: Item Weight Value 1 6 30 2 8 40 3 15 45 4 22 88 5 25 80 Allowed weight = 60 Kg Problem 3: Item Weight Value 1     6 30 2     8 40 3    15 45 4    22 88...
Solve the following initial value problem ?′′ + 3??′ + 2? = 0, ?(0) = 1...
Solve the following initial value problem ?′′ + 3??′ + 2? = 0, ?(0) = 1 and ?′(0) = 1 by using a power series ?0 + ?1? + ?2?2 + ?3?3 + ?4?4.
1. Solve the following initial value problem using Laplace transforms. d^2y/dt^2+ y = g(t) with y(0)=0...
1. Solve the following initial value problem using Laplace transforms. d^2y/dt^2+ y = g(t) with y(0)=0 and dy/dt(0) = 1 where g(t) = t/2 for 0<t<6 and g(t) = 3 for t>6
1. Consider the following integer programming problem. Z = 5x + y Subject to: (1) -x...
1. Consider the following integer programming problem. Z = 5x + y Subject to: (1) -x +2y ? 4 (2) x – y ? 1 (3) 4x + y ? 12 a) Solve this problem in Excel b) Solve this problem graphically. Label your optimal point and objective on your plot.
1.For the following linear programming problem Max 5X + 7Y s.t. 1X+ 1Y≤ 6 3X +1Y...
1.For the following linear programming problem Max 5X + 7Y s.t. 1X+ 1Y≤ 6 3X +1Y ≤ 12 X+ 2Y ≤ 10 X, Y ≥ 0 a)Write the problem in standard form. b)Solve the problem neatly using the graphical solution procedure(on paper). c)What are the values of the three slack variables at the optimal solution? d)Solve the problem with Microsoft Excel and attach your “own” printout.
Solve the following initial value problem: x2y′′+xy′−9y=0; y(1) = 6; y′(1) = 12
Solve the following initial value problem: x2y′′+xy′−9y=0; y(1) = 6; y′(1) = 12
5. Perform the following operations on the vectors u=(-4, 0, 2), v=(-1, -5, -4), and w=(0,...
5. Perform the following operations on the vectors u=(-4, 0, 2), v=(-1, -5, -4), and w=(0, 3, 4) u*w= (u*v)u= ((w*w)u)*u= u*v+v*w=
Solve the initial value problem. (?2+1)?′+2?=1+?where?(0)=2(x2+1)y′+2y=1+xwherey(0)=2
Solve the initial value problem. (?2+1)?′+2?=1+?where?(0)=2(x2+1)y′+2y=1+xwherey(0)=2
Redo Problem #5 using Excel. You should enter formulas in columns E and F to find...
Redo Problem #5 using Excel. You should enter formulas in columns E and F to find the TR and MRPL. How many workers should be hired. Workers TP P TR=TP(P) MRPL=Change in TR/Change in L MRCL=w 0 0 10 40 1 12 10 40 2 22 10 40 3 30 10 40 4 36 10 40 5 40 10 40 6 42 10 40
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT