Knapsack problem/0-1: Difference between revisions
Content added Content deleted
(Knapsack problem/0-1 in QBasic and Yabasic) |
|||
Line 1,097: | Line 1,097: | ||
}</lang> |
}</lang> |
||
("Bag" might not be the best name for the class, since "bag" is sometimes also used to refer to a multiset data structure.) |
("Bag" might not be the best name for the class, since "bag" is sometimes also used to refer to a multiset data structure.) |
||
=={{header|C#}}== |
|||
{{NAME|C#}} |
|||
C# Knapsak 0-1 Russian Binary ciphers |
|||
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 |
|||
<lang QB64> using System;using System.Text; // KNAPSACK 0-1 DANILIN |
|||
namespace Knapsack { class Program { static void Main() |
|||
{ int n=5; int G=5; int u=n+1; int a=Convert.ToInt32(Math.Pow(2,u)); |
|||
int[] L = new int[n]; int[] C = new int[n]; int[] j = new int[n]; |
|||
int[] q = new int[a]; int[] S = new int[a]; int[] d = new int[a]; |
|||
int dec; int i; string[] e = new string[a]; |
|||
int h; int k; int aa; int max; int m; Random rand = new Random(); |
|||
for (i=0; i<n; i++) // https://rextester.com//KNADH83291 |
|||
{L[i]=1+rand.Next(3); C[i]=10+rand.Next(9); |
|||
Console.Write(i+1); Console.Write(" "); |
|||
Console.Write(L[i]); Console.Write(" "); |
|||
Console.Write(C[i]);Console.WriteLine(); |
|||
} Console.WriteLine(); |
|||
for (h = a-1; h>(a-1)/2; h--) |
|||
{ dec=h; while (dec > 0) |
|||
{ e[h] = dec % 2 + e[h]; dec/=2; } |
|||
if (e[h] == "") {e[h] = "0";} |
|||
e[h]=e[h].Substring(1,e[h].Length-1); |
|||
for (k=0; k<n; k++) |
|||
{j[k]=Convert.ToInt32(e[h].Substring(k,1)); |
|||
q[h]=q[h]+L[k]*j[k]*C[k]; |
|||
d[h]=d[h]+L[k]*j[k];} |
|||
if (d[h]<= G) |
|||
{ Console.Write(G); Console.Write(" "); |
|||
Console.Write(d[h]); Console.Write(" "); |
|||
Console.Write(q[h]); Console.Write(" "); |
|||
Console.WriteLine(e[h]);} |
|||
} Console.WriteLine(); |
|||
max=0; m=1; |
|||
for (i=0; i<a; i++) |
|||
{ if (d[i]<=G && q[i]>max) |
|||
{ max=q[i]; m=i;}} |
|||
Console.Write(d[m]); Console.Write(" "); |
|||
Console.Write(q[m]); Console.Write(" "); |
|||
Console.WriteLine (e[m]);} |
|||
}}</lang> |
|||
{{out}} |
|||
<pre> # Mass Cost |
|||
1 2 12 |
|||
2 3 17 |
|||
3 1 14 |
|||
4 3 17 |
|||
5 1 13 |
|||
Chifer Mass Cost |
|||
11000 5 5 75 |
|||
01001 5 4 64 |
|||
00111 5 5 78 !!! |
|||
00110 5 4 65 |
|||
00101 5 2 27 |
|||
Mass MAX Chifer |
|||
5 78 00111</pre> |
|||
=={{header|C++}}== |
=={{header|C++}}== |