Knapsack 0-1 C# binary & rosettacode & WE

Knapsack 0-1 C# binary & rosettacode & WE

Classic Knapsack problem is solved in many ways

Contents: rosettacode.org/wiki/Knapsack_problem
Long read: rosettacode.org/wiki/Knapsack_problem/0-1

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
and it is possible to divide only anyone will not understand

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]);}
}}

Main thing is very brief and clear to even all

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

 

new version

Code:

using System;        // Knapsack C# binary DANILIN
using System.Text;    // rextester.com/YRFA61366
namespace Knapsack
{
class Knapsack
    {
    static void Main()
        {
            int n = 7;
            int Inside = 5;
            int all=Convert.ToInt32(Math.Pow(2,(n+1)));
            int[] mass = new int[n];
            int[] cost = new int[n];
            int[] jack = new int[n];
            int[] quality = new int[all];
            int[] amount = new int[all];  
            int i;             // circle
            int k;             // circle
            int dec;
            string[] bin = new string[all];
            int list;
            int max;
            int max_num;
            Random rand = new Random();

            for (i=0; i<n; i++)
            {
                mass[i]=1+rand.Next(3);
                cost[i]=10+rand.Next(9);
                Console.WriteLine("{0} {1} {2}", i+1, mass[i], cost[i]);
            }
            Console.WriteLine();

            for (list = all-1; list>(all-1)/2; list--)
            {
                dec=list;
                while (dec > 0)
                {
                    bin[list] = dec % 2 + bin[list]; // from 10 to 2
                    dec/=2;
                }
                if (bin[list] == "")
                {
                    bin[list] = "0";
                }
                bin[list]=bin[list].Substring(1,bin[list].Length-1);
                for (k=0; k<n; k++) // inside 01
                {
                    jack[k]=Convert.ToInt32(bin[list].Substring(k,1));
                    quality[list]=quality[list]+mass[k]*jack[k]*cost[k];     // integral of costs
                    amount[list]=amount[list]+mass[k]*jack[k];     // integral of mass
                }      
                if (amount[list]<= Inside)        // current mass < Knapsack
                {
                    Console.WriteLine("{0} {1} {2} {3}", Inside, amount[list], quality[list], bin[list]);
                }
            }
            Console.WriteLine();

            max=0;
            max_num=1;
            for (i=0; i < all; i++)
            {
                if (amount[i]<=Inside && quality[i]>max)
                {
                    max = quality[i]; max_num =i ;
                }
            }
            Console.WriteLine("{0} {1} {2}",amount[max_num],quality[max_num],bin[max_num]);
        }
    }
}