215 lines
9.1 KiB
VB.net
215 lines
9.1 KiB
VB.net
' Knapsack problem/0-1 - 13/02/2017
|
|
dim w(22),v(22),m(22)
|
|
data=array( "map", 9, 150, "compass", 13, 35, "water", 153, 200, _
|
|
"sandwich", 50, 160 , "glucose", 15, 60, "tin", 68, 45, _
|
|
"banana", 27, 60, "apple", 39, 40 , "cheese", 23, 30, "beer", 52, 10, _
|
|
"suntan cream", 11, 70, "camera", 32, 30 , "T-shirt", 24, 15, _
|
|
"trousers", 48, 10, "umbrella", 73, 40, "book", 30, 10 , _
|
|
"waterproof trousers", 42, 70, "waterproof overclothes", 43, 75 , _
|
|
"note-case", 22, 80, "sunglasses", 7, 20, "towel", 18, 12, "socks", 4, 50)
|
|
ww=400
|
|
xw=0:iw=0:iv=0
|
|
w(1)=iw:v(1)=iv
|
|
for i1=0 to 1:m(1)=i1:j=0
|
|
if i1=1 then
|
|
iw=w(1)+data(j*3+1):iv=v(1)+data(j*3+2)
|
|
if iv>xv and iw<=ww then xw=iw:xv=iv:l=m
|
|
end if 'i1
|
|
if iw<=ww then
|
|
w(2)=iw: v(2)=iv
|
|
for i2=0 to 1:m(2)=i2:j=1
|
|
if i2=1 then
|
|
iw=w(2)+data(j*3+1):iv=v(2)+data(j*3+2)
|
|
if iv>xv and iw<=ww then xw=iw:xv=iv:l=m
|
|
end if 'i2
|
|
if iw<=ww then
|
|
w(3)=iw: v(3)=iv
|
|
for i3=0 to 1:m(3)=i3:j=2
|
|
if i3=1 then
|
|
iw=w(3)+data(j*3+1):iv=v(3)+data(j*3+2)
|
|
if iv>xv and iw<=ww then xw=iw:xv=iv:l=m
|
|
end if 'i3
|
|
if iw<=ww then
|
|
w(4)=iw: v(4)=iv
|
|
for i4=0 to 1:m(4)=i4:j=3
|
|
if i4=1 then
|
|
iw=w(4)+data(j*3+1):iv=v(4)+data(j*3+2)
|
|
if iv>xv and iw<=ww then xw=iw:xv=iv:l=m
|
|
end if 'i4
|
|
if iw<=ww then
|
|
w(5)=iw: v(5)=iv
|
|
for i5=0 to 1:m(5)=i5:j=4
|
|
if i5=1 then
|
|
iw=w(5)+data(j*3+1):iv=v(5)+data(j*3+2)
|
|
if iv>xv and iw<=ww then xw=iw:xv=iv:l=m
|
|
end if 'i5
|
|
if iw<=ww then
|
|
w(6)=iw: v(6)=iv
|
|
for i6=0 to 1:m(6)=i6:j=5
|
|
if i6=1 then
|
|
iw=w(6)+data(j*3+1):iv=v(6)+data(j*3+2)
|
|
if iv>xv and iw<=ww then xw=iw:xv=iv:l=m
|
|
end if 'i6
|
|
if iw<=ww then
|
|
w(7)=iw: v(7)=iv
|
|
for i7=0 to 1:m(7)=i7:j=6
|
|
if i7=1 then
|
|
iw=w(7)+data(j*3+1):iv=v(7)+data(j*3+2)
|
|
if iv>xv and iw<=ww then xw=iw:xv=iv:l=m
|
|
end if 'i7
|
|
if iw<=ww then
|
|
w(8)=iw: v(8)=iv
|
|
for i8=0 to 1:m(8)=i8:j=7
|
|
if i8=1 then
|
|
iw=w(8)+data(j*3+1):iv=v(8)+data(j*3+2)
|
|
if iv>xv and iw<=ww then xw=iw:xv=iv:l=m
|
|
end if 'i8
|
|
if iw<=ww then
|
|
w(9)=iw: v(9)=iv
|
|
for i9=0 to 1:m(9)=i9:j=8
|
|
if i9=1 then
|
|
iw=w(9)+data(j*3+1):iv=v(9)+data(j*3+2)
|
|
if iv>xv and iw<=ww then xw=iw:xv=iv:l=m
|
|
end if 'i9
|
|
if iw<=ww then
|
|
w(10)=iw: v(10)=iv
|
|
for i10=0 to 1:m(10)=i10:j=9
|
|
if i10=1 then
|
|
iw=w(10)+data(j*3+1):iv=v(10)+data(j*3+2)
|
|
if iv>xv and iw<=ww then xw=iw:xv=iv:l=m
|
|
end if 'i10
|
|
if iw<=ww then
|
|
w(11)=iw: v(11)=iv
|
|
for i11=0 to 1:m(11)=i11:j=10
|
|
if i11=1 then
|
|
iw=w(11)+data(j*3+1):iv=v(11)+data(j*3+2)
|
|
if iv>xv and iw<=ww then xw=iw:xv=iv:l=m
|
|
end if 'i11
|
|
if iw<=ww then
|
|
w(12)=iw: v(12)=iv
|
|
for i12=0 to 1:m(12)=i12:j=11
|
|
if i12=1 then
|
|
iw=w(12)+data(j*3+1):iv=v(12)+data(j*3+2)
|
|
if iv>xv and iw<=ww then xw=iw:xv=iv:l=m
|
|
end if 'i12
|
|
if iw<=ww then
|
|
w(13)=iw: v(13)=iv
|
|
for i13=0 to 1:m(13)=i13:j=12
|
|
if i13=1 then
|
|
iw=w(13)+data(j*3+1):iv=v(13)+data(j*3+2)
|
|
if iv>xv and iw<=ww then xw=iw:xv=iv:l=m
|
|
end if 'i13
|
|
if iw<=ww then
|
|
w(14)=iw: v(14)=iv
|
|
for i14=0 to 1:m(14)=i14:j=13
|
|
if i14=1 then
|
|
iw=w(14)+data(j*3+1):iv=v(14)+data(j*3+2)
|
|
if iv>xv and iw<=ww then xw=iw:xv=iv:l=m
|
|
end if 'i14
|
|
if iw<=ww then
|
|
w(15)=iw: v(15)=iv
|
|
for i15=0 to 1:m(15)=i15:j=14
|
|
if i15=1 then
|
|
iw=w(15)+data(j*3+1):iv=v(15)+data(j*3+2)
|
|
if iv>xv and iw<=ww then xw=iw:xv=iv:l=m
|
|
end if 'i15
|
|
if iw<=ww then
|
|
w(16)=iw: v(16)=iv
|
|
for i16=0 to 1:m(16)=i16:j=15
|
|
if i16=1 then
|
|
iw=w(16)+data(j*3+1):iv=v(16)+data(j*3+2)
|
|
if iv>xv and iw<=ww then xw=iw:xv=iv:l=m
|
|
end if 'i16
|
|
if iw<=ww then
|
|
w(17)=iw: v(17)=iv
|
|
for i17=0 to 1:m(17)=i17:j=16
|
|
if i17=1 then
|
|
iw=w(17)+data(j*3+1):iv=v(17)+data(j*3+2)
|
|
if iv>xv and iw<=ww then xw=iw:xv=iv:l=m
|
|
end if 'i17
|
|
if iw<=ww then
|
|
w(18)=iw: v(18)=iv
|
|
for i18=0 to 1:m(18)=i18:j=17
|
|
if i18=1 then
|
|
iw=w(18)+data(j*3+1):iv=v(18)+data(j*3+2)
|
|
if iv>xv and iw<=ww then xw=iw:xv=iv:l=m
|
|
end if 'i18
|
|
if iw<=ww then
|
|
w(19)=iw: v(19)=iv
|
|
for i19=0 to 1:m(19)=i19:j=18
|
|
if i19=1 then
|
|
iw=w(19)+data(j*3+1):iv=v(19)+data(j*3+2)
|
|
if iv>xv and iw<=ww then xw=iw:xv=iv:l=m
|
|
end if 'i19
|
|
if iw<=ww then
|
|
w(20)=iw: v(20)=iv
|
|
for i20=0 to 1:m(20)=i20:j=19
|
|
if i20=1 then
|
|
iw=w(20)+data(j*3+1):iv=v(20)+data(j*3+2)
|
|
if iv>xv and iw<=ww then xw=iw:xv=iv:l=m
|
|
end if 'i20
|
|
if iw<=ww then
|
|
w(21)=iw: v(21)=iv
|
|
for i21=0 to 1:m(21)=i21:j=20
|
|
if i21=1 then
|
|
iw=w(21)+data(j*3+1):iv=v(21)+data(j*3+2)
|
|
if iv>xv and iw<=ww then xw=iw:xv=iv:l=m
|
|
end if 'i21
|
|
if iw<=ww then
|
|
w(22)=iw: v(22)=iv
|
|
for i22=0 to 1:m(22)=i22:j=21
|
|
nn=nn+1
|
|
if i22=1 then
|
|
iw=w(22)+data(j*3+1):iv=v(22)+data(j*3+2)
|
|
if iv>xv and iw<=ww then xw=iw:xv=iv:l=m
|
|
end if 'i22
|
|
if iw<=ww then
|
|
end if 'i22
|
|
next:m(22)=0
|
|
end if 'i21
|
|
next:m(21)=0
|
|
end if 'i20
|
|
next:m(20)=0
|
|
end if 'i19
|
|
next:m(19)=0
|
|
end if 'i18
|
|
next:m(18)=0
|
|
end if 'i17
|
|
next:m(17)=0
|
|
end if 'i16
|
|
next:m(16)=0
|
|
end if 'i15
|
|
next:m(15)=0
|
|
end if 'i14
|
|
next:m(14)=0
|
|
end if 'i13
|
|
next:m(13)=0
|
|
end if 'i12
|
|
next:m(12)=0
|
|
end if 'i11
|
|
next:m(11)=0
|
|
end if 'i10
|
|
next:m(10)=0
|
|
end if 'i9
|
|
next:m(9)=0
|
|
end if 'i8
|
|
next:m(8)=0
|
|
end if 'i7
|
|
next:m(7)=0
|
|
end if 'i6
|
|
next:m(6)=0
|
|
end if 'i5
|
|
next:m(5)=0
|
|
end if 'i4
|
|
next:m(4)=0
|
|
end if 'i3
|
|
next:m(3)=0
|
|
end if 'i2
|
|
next:m(2)=0
|
|
end if 'i1
|
|
next:m(1)=0
|
|
for i=1 to 22
|
|
if l(i)=1 then wlist=wlist&vbCrlf&data((i-1)*3)
|
|
next
|
|
Msgbox mid(wlist,3)&vbCrlf&vbCrlf&"weight="&xw&vbCrlf&"value="&xv,,"Knapsack - nn="&nn
|