Latihan 0/1 Knapsack Problem


Pseudocode 0/1 Knapsack Problem :

for w=0 to Wmax do

K[0,w]=0

end for

for i=1 to n do

K[i,0]=0

end for

for i=1 to n do

for w=0 to Wmax do

if w[i]<=w then

if b[i]+K[i-1,w-w[i]]>K[i-1,w] then

K[i,w]=b[i]+K[i-1,w-w[i]]

else

K[i,w]=K[i-1,w]

end if

else

K[i,w]=K[i-1,w]

end if

end for

end for

Pseudocode mencari barang yang dibawa :

i=n

x=W

while K[i,x]>0 do

if K[i,x]<>K[i-1,x] then

mark item i in the knapsack

x=x–w[i]

i=i–1

else

i=i-1

end if

end while

Soal 1

IMG_20131230_115405

IMG_20131230_115605

IMG_20131230_115757

IMG_20131230_115630

IMG_20131230_115643

IMG_20131230_115651

IMG_20131230_115701

Soal 2

IMG_20131230_143512

IMG_20131230_143525

IMG_20131230_143536

Advertisements

One thought on “Latihan 0/1 Knapsack Problem

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s