Knapsack 0-1 JavaScript binary & rosettacode & WE
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
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
Code:
<!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>
Code:
# 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