Knapsack 0-1 & rosettacode & qbasic qb64 & WE

[DANILIN]

Knapsack 0-1 & rosettacode & qbasic qb64 & WE

For all people: send yours algorithms to rosettacode
otherwise forum may disappear even in google search

Classic Knapsack problem is solved in many ways

Contents: http://rosettacode.org/wiki/Knapsack_problem
Long read: rosettacode.org/wiki/Knapsack_problem/0-1

Previous topics and long programs: Knapsack
https://qb64forum.alephc.xyz/index.php?topic=3091
Ordered Combinations Generator
https://qb64forum.alephc.xyz/index.php?topic=2999

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 write results to qb64 directory

Code: (Select All)

Open "knapsack.txt" For Output As #1
N=7: L=5: a = 2^(N+1): Randomize Timer 'knapsack.bas DANILIN
Dim L(N), C(N), j(N), q(a), q$(a), d(a)

For m=a-1 To (a-1)/2 Step -1: g=m: Do ' sintez shifr
    q$(m)=LTrim$(Str$(g Mod 2))+q$(m)
    g=g\2: Loop Until g=0
    q$(m)=Mid$(q$(m), 2, Len(q$(m)))
Next

For i=1 To N: L(i)=Int(Rnd*3+1) ' lenght & cost
C(i)=10+Int(Rnd*9): Print #1, i, L(i), C(i): Next ' origin

For h=a-1 To (a-1)/2 Step -1
    For k=1 To N: j(k)=Val(Mid$(q$(h), k, 1)) ' from shifr
        q(h)=q(h)+L(k)*j(k)*C(k) ' 0 or 1
        d(h)=d(h)+L(k)*j(k)
    Next
    If d(h) <= L Then Print #1, d(h), q(h), q$(h)
Next
max=0: m=1: For i=1 To a
    If d(i)<=L Then If q(i) > max Then max=q(i): m=i
Next
Print #1,: Print #1, d(m), q(m), q$(m): End

Main thing is very brief and clear to even all

Results is reduced manually:

Code: (Select All)

1             2             17
2             2             14
3             2             17
4             1             11
5             2             18
6             3             14
7             3             10

5             73           1101000
4             62           1100000
2             28           0100000
5             81           0011100 !!!
3             45           0011000
5             76           0010010
2             36           0000100

5             81           0011100