Knapsack problem/0-1: Difference between revisions
no edit summary
m (→{{header|Picat}}: Adding {{out}}) |
No edit summary |
||
Line 5,771:
TOTALS: 396 1030
</pre>
=={{header|QB64}}==
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
Program write results to qb64 directory
<lang QB64>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 ' cipher 0-1
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) ' mass & 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)) ' j() = cipher
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</lang>
<lang QB64>Main thing is very brief and clear to even all
Results is reduced manually:
</lang>
{{out}}
<pre> # Mass Cost
1 2 17
2 2 14
3 2 17
4 1 11
5 2 18
6 3 14
7 3 10
Mass Cost Chifer
5 73 1101000
2 28 0100000
5 81 0011100 !!!
3 45 0011000
5 76 0010010
2 36 0000100
Mass MAX Chifer
5 81 0011100</pre>
=={{header|Python}}==
| |||