May-29-2022, 07:30 AM
Knapsack 0-1 & python & qbasic qb64 & WE
Classic Knapsack problem is solved in many ways
Contents: http://rosettacode.org/wiki/Knapsack_problem
Long read: rosettacode.org/wiki/Knapsack_problem/0-1
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=5 N!=120 >> 2^N=32
Random values origin are automatically assigned quantity and quality
and integral of value is obtained and in general: integral of quantity and quality
and it is possible to divide only anyone will not understand
Program qb64 write results to directory
Main thing is very brief and clear to even all
Classic Knapsack problem is solved in many ways
Contents: http://rosettacode.org/wiki/Knapsack_problem
Long read: rosettacode.org/wiki/Knapsack_problem/0-1
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=5 N!=120 >> 2^N=32
Random values origin are automatically assigned quantity and quality
and integral of value is obtained and in general: integral of quantity and quality
and it is possible to divide only anyone will not understand
Program qb64 write results to directory
Main thing is very brief and clear to even all
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
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 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) print () for h in range (a - 1 ,(a - 1 ) / / 2 , - 1 ): # For h=a-1 To 0 Step -1 # b = str ( bin (h)) e[h] = b[ 3 : len (b)] # binary without origin 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 #print(e[h],L[k],j[k],C[k],d[h], q[h]) 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 |
Output:# 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
Only Knapsack 0-1 binary Python1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
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]) |
Russia looks world from future. Big data is peace data
Nobel Prize will not receive itself
Nobelevskaya premiya sama sebya ne poluchit
Нобелевская премия сама себя не получит
Le prix Nobel ne se recevra pas
Nobelpreis wird sich nicht erhalten
Il Premio Nobel non ricevera se stesso
Nobel Prize will not receive itself
Nobelevskaya premiya sama sebya ne poluchit
Нобелевская премия сама себя не получит
Le prix Nobel ne se recevra pas
Nobelpreis wird sich nicht erhalten
Il Premio Nobel non ricevera se stesso