Classic Knapsack problem is solved in many ways
My newest program synthesizes all ciphers from 0 & 1
adding an extra register and 0 remain on left in cipher
Number of comparisons decreases from N! to 2^N
for example N=10 & N!=3628800 >> 2^N=1024
Random values origin are automatically assigned
quantity and quality and integral of value is obtained
and in general: integral of quantity and quality
Expand|Select|Wrap|Line Numbers
- 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])
Results is reduced manually:
Expand|Select|Wrap|Line Numbers
- # Mass Cost
- 1 2 12
- 2 3 17
- 3 1 14
- 4 3 17
- 5 1 13
- Chifer Mass Cost
- 11000 5 5 75
- 01001 5 4 64
- 00111 5 5 78 !!!
- 00110 5 4 65
- 00101 5 2 27
- Mass MAX Chifer
- 5 78 00111