n=5; N=n+1; G=5; a=2**N	# KNAPSACK 0-1 DANILIN 
L=[];C=[];e=[];j=[];q=[];s=[] # rextester.com/BCKP19591
d=[];L=[1]*n;C=[1]*n;e=[1]*a	
j=[1]*n;q=[0]*a;s=[0]*a;d=[0]*a
 
from random import randint
for i in range(0,n):
    L[i]=randint(1,3)
    C[i]=10+randint(1,9)
    print(i+1,L[i],C[i])
print()
 
for h in range(a-1,(a-1)//2,-1):
    b=str(bin(h))
    e[h]=b[3:len(b)]
 
    for k in range (n):
        j[k]=int(e[h][k])
        q[h]=q[h]+L[k]*j[k]*C[k]
        d[h]=d[h]+L[k]*j[k]
 
    if d[h]<= G:
        print(e[h], G, d[h], q[h])
print()   
 
max=0; m=1 
for i in range(a):
    if d[i]<=G and q[i]>max:
        max=q[i]; m=i	
print (d[m], q[m], e[m])
 

bj01OyBOPW4rMTsgRz01OyBhPTIqKk4JIyBLTkFQU0FDSyAwLTEgREFOSUxJTiAKTD1bXTtDPVtdO2U9W107aj1bXTtxPVtdO3M9W10gIyByZXh0ZXN0ZXIuY29tL0JDS1AxOTU5MQpkPVtdO0w9WzFdKm47Qz1bMV0qbjtlPVsxXSphCQpqPVsxXSpuO3E9WzBdKmE7cz1bMF0qYTtkPVswXSphCgpmcm9tIHJhbmRvbSBpbXBvcnQgcmFuZGludApmb3IgaSBpbiByYW5nZSgwLG4pOgogICAgTFtpXT1yYW5kaW50KDEsMykKICAgIENbaV09MTArcmFuZGludCgxLDkpCiAgICBwcmludChpKzEsTFtpXSxDW2ldKQpwcmludCgpCgpmb3IgaCBpbiByYW5nZShhLTEsKGEtMSkvLzIsLTEpOgogICAgYj1zdHIoYmluKGgpKQogICAgZVtoXT1iWzM6bGVuKGIpXQogICAgICAgIAogICAgZm9yIGsgaW4gcmFuZ2UgKG4pOgogICAgICAgIGpba109aW50KGVbaF1ba10pCiAgICAgICAgcVtoXT1xW2hdK0xba10qaltrXSpDW2tdCiAgICAgICAgZFtoXT1kW2hdK0xba10qaltrXQogICAgICAgIAogICAgaWYgZFtoXTw9IEc6CiAgICAgICAgcHJpbnQoZVtoXSwgRywgZFtoXSwgcVtoXSkKcHJpbnQoKSAgIAoKbWF4PTA7IG09MSAKZm9yIGkgaW4gcmFuZ2UoYSk6CiAgICBpZiBkW2ldPD1HIGFuZCBxW2ldPm1heDoKICAgICAgICBtYXg9cVtpXTsgbT1pCQpwcmludCAoZFttXSwgcVttXSwgZVttXSkK