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
Copy & Save as & Run
KnapSackDa.htm
Expand|Select|Wrap|Line Numbers
- <!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8">
- <meta name="viewport" content="width=device-width, initial-scale=1.0">
- <meta http-equiv="X-UA-Compatible" content="ie=edge">
- <title>KNAPSACK JavaScript</title> </head> <body> <noscript>Vkluch JS</noscript>
- jdoodle.com/h/2Uc
- rextester.com/BQYV50962
- <script>
- var n=12; G=2; a = Math.pow(2,n+1); // KNAPSACKj.js
- var dec, i, h, k, max, m, s;
- var L=[n], C=[n], j=[n], q=[a], d=[a]; e=[a];
- document.write("<br><br># Kol Cena<br>")
- document.write("# Amo Price<br><br>")
- for (i=0; i<n; i++)
- { L[i]=1+Math.floor(Math.random()*3)
- C[i]=10+Math.floor(Math.random()*9); j[i]=0;
- document.write( (i+1) +" "+ L[i] +" "+ C[i] +"<br>")
- }
- for (i=0; i<a; i++) { q[i]=0; d[i]=0;}
- document.write("<br>")
- document.write("Mx Kol St-st Schifr<br>")
- document.write("Mx Amo Price Chifer<br>")
- for (h = a-1; h>(a-1)/2; h--)
- { dec=h; e[h]=""
- while (dec > 0)
- { s = Math.floor(dec % 2);
- e[h] = s + e[h]; dec = Math.floor(dec/2);
- }
- if (e[h] == "") {e[h] = "0";}
- e[h]= e[h].substr(1, e[h].length-1);
- for (k=0; k<n; k++)
- { j[k] = Number(e[h].substr(k,1));
- q[h]=q[h]+L[k]*j[k]*C[k];
- d[h]=d[h]+L[k]*j[k];
- }
- if (d[h] <= G)
- document.write("<br>"+ G +" "+ d[h] +" "+ q[h] +" "+ e[h])
- } document.write("<br>")
- max=0; m=1;
- for (i=0; i<a; i++)
- { if (d[i]<=G && q[i]>max){ max=q[i]; m=i;}
- }
- document.write("<br>"+ d[m] +" "+ q[m] +" "+ e[m] +"<br><br>")
- document.write("Mx St-st Schifr<br>")
- document.write("Mx Price Cipher<br><br>")
- </script>
- </body> </html>
Expand|Select|Wrap|Line Numbers
- # Kol Cena
- # Amo Price
- 1 1 10
- 2 3 13
- 3 2 17
- 4 3 12
- 5 3 15
- Mx Kol St-st Schifr
- Mx Amo Price Chifer
- 3 3 44 10100
- 3 1 10 10000
- 3 3 39 01000
- 3 2 34 00100
- 3 3 36 00010
- 3 3 45 00001
- 3 0 0 00000
- 3 45 00001
- Mx St-st Schifr
- Mx Price Cipher