Knapsack problem/0-1: Difference between revisions
→Recursive dynamic programming algorithm
No edit summary |
|||
Line 5,975:
print "value:", total_value(solution, max_weight)
print "weight:", sum([x[1] for x in solution])</lang>
===Python Russian Binary ciphers===
Russian Knapsack 0-1 synthesizes all ciphers from 0 & 1 adding left +1 register and 0 remain on left in cipher
Number of comparisons decreases from N! to 2^N for example N=8 N!=40320 >> 2^N=256
Random values origin are automatically assigned create integral of quantity and quality
<lang python>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])</lang>
{{out}}
<pre># Mass Cost
1 2 12
2 3 17
3 1 14
4 3 17
5 1 13
Chifer Mass Cost
11000 5 5 75
10101 5 4 51
01001 5 4 64
00111 5 5 78 !!!
00110 5 4 65
00101 5 2 27
00000 5 0 0
Mass MAX Chifer
5 78 00111</pre>
=={{header|R}}==
| |||