# Knapsack 0-1 C# binary & rosettacode & WE

Discussion in 'C#' started by DANILIN, Jun 1, 2022.

Tags:
1. ### DANILINNew Member

Joined:
Oct 24, 2018
Messages:
6
4
Trophy Points:
3
Gender:
Male
Knapsack 0-1 C# binary & rosettacode & WE

Classic Knapsack problem is solved in many ways

Contents: rosettacode.org/wiki/Knapsack_problem

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```

shabbir likes this.
2. ### DANILINNew Member

Joined:
Oct 24, 2018
Messages:
6
4
Trophy Points:
3
Gender:
Male
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]);
}
}
}```

shabbir likes this.