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
Expand|Select|Wrap|Line Numbers
- 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 max; int m; Random rand = new Random();
- for (i=0; i<n; i++) // rextester.com/OIALC94208
- {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]);}
- }}
Results is reduced manually:
Expand|Select|Wrap|Line Numbers
- # 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