Knapsack 0-1 Python binary & rosettacode & WE
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
Main thing is very brief and clear to even all
Results is reduced manually:
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
Code:
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:
Code:
# 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