Knapsack 0-1 C# 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
Main thing is very brief and clear to even all
Results is reduced manually:
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
Code:
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:
Code:
# 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
Comment