n=5; N=n+1; G=5; a=2**N			# N=7: L=5: a = 2^(N+1): 'knapsack.bas DANILIN
L=[];C=[];e=[];j=[];q=[];s=[]		# Dim L(N), C(N), j(N), q(a), q$(a), d(a)
d=[];L=[1]*n;C=[1]*n;e=[1]*a		# KNAPSACK 0-1 DANILIN
j=[1]*n;q=[0]*a;s=[0]*a;d=[0]*a
 
from random import randint	# Randomize Timer 
for i in range(0,n):		# For i=1 To N 
    L[i]=randint(1,3)		# L(i)=Int(Rnd*3+1) 
    C[i]=10+randint(1,9)		# C(i)=10+Int(Rnd*9) 
    print(i+1,L[i],C[i])		# Print i, L(i), C(i): Next
print()
 
for h in range(a-1,(a-1)//2,-1):	# For m=a-1 To (a-1)/2 Step -1: g=m: Do
    b=str(bin(h))				# q$(m)=LTrim$(Str$(g Mod 2))+q$(m): g=g\2: Loop Until g=0
    e[h]=b[3:len(b)]			# q$(m)=Mid$(q$(m), 2, Len(q$(m))): Next
 
    for k in range (n):			# For k=1 To N:
      j[k]=int(e[h][k])			# j(k)=Val(Mid$(q$(h), k, 1)) ' from chifer
      q[h]=q[h]+L[k]*j[k]*C[k]	# q(h)=q(h)+L(k)*j(k)*C(k) ' 0 or 1
      d[h]=d[h]+L[k]*j[k]		# d(h)=d(h)+L(k)*j(k): Next
 
    if d[h]<= G:				# If d(h) <= L Then 
      print(e[h], G, d[h],q[h])	# Print #1, d(h), q(h), q$(h): Next
print()   
 
max=0; m=1 				# max=0: m=1: 
for i in range(a):			# For i=1 To a
    if d[i]<=G and q[i]>max:	# If d(i)<=L Then If q(i) > max 
        max=q[i]; m=i		# Then max=q(i): m=i: Next
print (d[m], q[m], e[m])		# Print #1,: Print #1, d(m), q(m), q$(m): End
 
 

bj01OyBOPW4rMTsgRz01OyBhPTIqKk4JCQkjIE49NzogTD01OiBhID0gMl4oTisxKTogJ2tuYXBzYWNrLmJhcyBEQU5JTElOCkw9W107Qz1bXTtlPVtdO2o9W107cT1bXTtzPVtdCQkjIERpbSBMKE4pLCBDKE4pLCBqKE4pLCBxKGEpLCBxJChhKSwgZChhKQpkPVtdO0w9WzFdKm47Qz1bMV0qbjtlPVsxXSphCQkjIEtOQVBTQUNLIDAtMSBEQU5JTElOCmo9WzFdKm47cT1bMF0qYTtzPVswXSphO2Q9WzBdKmEKCmZyb20gcmFuZG9tIGltcG9ydCByYW5kaW50CSMgUmFuZG9taXplIFRpbWVyIApmb3IgaSBpbiByYW5nZSgwLG4pOgkJIyBGb3IgaT0xIFRvIE4gCiAgICBMW2ldPXJhbmRpbnQoMSwzKQkJIyBMKGkpPUludChSbmQqMysxKSAKICAgIENbaV09MTArcmFuZGludCgxLDkpCQkjIEMoaSk9MTArSW50KFJuZCo5KSAKICAgIHByaW50KGkrMSxMW2ldLENbaV0pCQkjIFByaW50IGksIEwoaSksIEMoaSk6IE5leHQKcHJpbnQoKQoKZm9yIGggaW4gcmFuZ2UoYS0xLChhLTEpLy8yLC0xKToJIyBGb3IgbT1hLTEgVG8gKGEtMSkvMiBTdGVwIC0xOiBnPW06IERvCiAgICBiPXN0cihiaW4oaCkpCQkJCSMgcSQobSk9TFRyaW0kKFN0ciQoZyBNb2QgMikpK3EkKG0pOiBnPWdcMjogTG9vcCBVbnRpbCBnPTAKICAgIGVbaF09YlszOmxlbihiKV0JCQkjIHEkKG0pPU1pZCQocSQobSksIDIsIExlbihxJChtKSkpOiBOZXh0CiAgICAgICAgCiAgICBmb3IgayBpbiByYW5nZSAobik6CQkJIyBGb3Igaz0xIFRvIE46CiAgICAgIGpba109aW50KGVbaF1ba10pCQkJIyBqKGspPVZhbChNaWQkKHEkKGgpLCBrLCAxKSkgJyBmcm9tIGNoaWZlcgogICAgICBxW2hdPXFbaF0rTFtrXSpqW2tdKkNba10JIyBxKGgpPXEoaCkrTChrKSpqKGspKkMoaykgJyAwIG9yIDEKICAgICAgZFtoXT1kW2hdK0xba10qaltrXQkJIyBkKGgpPWQoaCkrTChrKSpqKGspOiBOZXh0CiAgICAgICAgCiAgICBpZiBkW2hdPD0gRzoJCQkJIyBJZiBkKGgpIDw9IEwgVGhlbiAKICAgICAgcHJpbnQoZVtoXSwgRywgZFtoXSxxW2hdKQkjIFByaW50ICMxLCBkKGgpLCBxKGgpLCBxJChoKTogTmV4dApwcmludCgpICAgCgptYXg9MDsgbT0xIAkJCQkjIG1heD0wOiBtPTE6IApmb3IgaSBpbiByYW5nZShhKToJCQkjIEZvciBpPTEgVG8gYQogICAgaWYgZFtpXTw9RyBhbmQgcVtpXT5tYXg6CSMgSWYgZChpKTw9TCBUaGVuIElmIHEoaSkgPiBtYXggCiAgICAgICAgbWF4PXFbaV07IG09aQkJIyBUaGVuIG1heD1xKGkpOiBtPWk6IE5leHQKcHJpbnQgKGRbbV0sIHFbbV0sIGVbbV0pCQkjIFByaW50ICMxLDogUHJpbnQgIzEsIGQobSksIHEobSksIHEkKG0pOiBFbmQKCg==