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

#### DANILIN

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

Classic Knapsack problem is solved in many ways

Contents: Knapsack problem - Rosetta Code

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

C#:
``````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:

C#:
``````# 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``````

Last edited:
Solution
Now my design visually right observer of margins

1 is added to left and investigated
111 110 101 100

Right part is taken from them
11 10 01 00
with all zeros

Where number of registers is equal to number of items

If you examine everything up to 0
then we'll get to options 1 and 0
what is less than number of items

Conclusion: now ciphers always correspond to subjects
and there is an implementation in Excel just a table

C#:
``````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)))...``````

#### Skydiver

Staff member
The only thing you are doing is using the binary representation of the combination number to generate which items to try putting into the knapsack. The only reason why the comparisons go down is because you add up all the masses and then compare to see if they fit in the knapsack while other approaches try to add items into the knapsack until it overflows. You simply substituted the number of comparisons with multiple additions and multiplications, then followed by a single comparisons.

As aside please use meaningful variable names. Please properly indent your code (preferably in Allman indent style).

• DANILIN

#### DANILIN

##### Active member
I indented my code in indent style
and commented variable names

C#:
``````using System;		// Knapsack C# binary DANILIN
using System.Text;	// rextester.com/MUTNY8650
namespace Knapsack
{
class Knapsack
{
static void Main()
{
int n=7; // number of elements
int G=5; // inside Knapsack
int u=n+1; // number for 2^
int a=Convert.ToInt32(Math.Pow(2,u)); // all elements
int[] L = new int[n]; // array of mass
int[] C = new int[n]; // array of costs
int[] j = new int[n]; // array of 0 or 1
int[] q = new int[a]; // integral of costs
int[] d = new int[a]; // integral of mass
int dec; 		// for 10 -> 2
int i; 			// circle
string[] e = new string[a]; // string from 01
int h; 			// circle lists
int k; 			// circle inside 01
int max; 		// maximum
int m; 			// number of maximum
Random rand = new Random();

for (i=0; i<n; i++)
{
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--) // all elements
{
dec=h;
while (dec > 0)
{
e[h] = dec % 2 + e[h]; // from 10 to 2
dec/=2;
}
if (e[h] == "")
{
e[h] = "0";
}
e[h]=e[h].Substring(1,e[h].Length-1);

for (k=0; k<n; k++) // inside 01
{
j[k]=Convert.ToInt32(e[h].Substring(k,1));
q[h]=q[h]+L[k]*j[k]*C[k]; 	// integral of costs
d[h]=d[h]+L[k]*j[k]; 	// integral of mass
}
if (d[h]<= G)		// current mass < Knapsack
{
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++)		// search of maximums
{
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]);
}
}
}``````

on other hand: guess all why variable is needed

Last edited:

#### Skydiver

Staff member
If you have to comment a variable, that is a code smell that you are not using meaningful variable names.

Last edited:
• DANILIN

#### Skydiver

Staff member
Why do you only check half of the combinations (e.g. `h: a-1..(a-1)/2`)?

• DANILIN

#### DANILIN

##### Active member
origin: "adding an extra register and 0 remain on left in cipher"

otherwise number of characters in cipher will decrease

plus meaningful variable names

C#:
``````using System;		// Knapsack C# binary DANILIN
using System.Text;	// rextester.com/SEUD75646
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.Write(i+1);
Console.Write("   ");
Console.Write(mass[i]);
Console.Write("   ");
Console.Write(cost[i]);
Console.WriteLine();
}
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.Write(Inside);
Console.Write("  ");
Console.Write(amount[list]);
Console.Write("  ");
Console.Write(quality[list]);
Console.Write("  ");
Console.WriteLine(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.Write(amount[max_num]);
Console.Write("  ");
Console.Write(quality[max_num]);
Console.Write("  ");
Console.WriteLine (bin[max_num]);
}
}
}``````

#### Skydiver

Staff member
Still terrible indentation. Example, the lines 41-68 are all in the body of the outer for loop at line 39, but that is not obvious when looking at the code.

Still not clear why you are going over that range from `all-1` down to `(all-1)/2`. Why not the entire range? Why not `0` up to `(all-1)/2`?

• DANILIN

#### Skydiver

Staff member
Here's my re-write of the code, but I go through the entire range of values instead of just the top half:
C#:
``````using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class ZeroOneKnapsack
{
const int ItemCount = 7;
const int MaxKnapsackMass = 5;

readonly static Item MinItem = new Item(Mass: 1, Cost: 10);
readonly static Item MaxItem = new Item(Mass: 10, Cost: 19);

static void Main()
{
var items = CreateItems(ItemCount).ToList();
for (int i = 0; i < items.Count; i++)
Console.WriteLine(\$"{i + 1}: {items[i]}");
Console.WriteLine();

var configurations = GenerateConfigurations(items).Where(c => c.Mass <= MaxKnapsackMass)
.ToList();
foreach(var configuration in configurations)
Console.WriteLine(configuration);
Console.WriteLine();

var maxConfiguration = configurations.OrderByDescending(c => c.MassCost)
.First();
Console.WriteLine(\$"{maxConfiguration}");

IEnumerable<Item> CreateItems(int maxItems)
{
Random rand = new Random();
for (int i = 0; i < maxItems; i++)
yield return new Item(Mass: rand.Next(MinItem.Mass, MaxItem.Mass),
Cost: rand.Next(MaxItem.Cost, MaxItem.Cost));
}

{
uint permutations = (uint)1 << items.Count - 1;
for (uint i = 0; i < permutations; i++)
yield return new Configuration(i, items);
}
}
}

record class Item(int Mass, int Cost);

class Configuration
{
public uint ConfigurationNumber { get; init; }
public int Cost { get; init; }
public int Mass { get; init; }
public int MassCost { get; init; }

int _itemCount;

{
ConfigurationNumber = configurationNumber;
_itemCount = items.Count();

int index = 0;
uint value = configurationNumber;
while (value > 0)
{
if (value % 2 == 1)
{
Cost += items[index].Cost;
Mass += items[index].Mass;
MassCost += items[index].Cost * items[index].Mass;
}
value /= 2;
index++;
}
}

public override string ToString()
{
var sb = new StringBuilder();
sb.Append("{ ");
sb.Append(\$"ConfigurationNumber = {ConfigurationNumber.ToBinaryString(_itemCount)}, ");
sb.Append(\$"Cost = {Cost}, ");
sb.Append(\$"Mass = {Mass}, ");
sb.Append(\$"MassCost = {MassCost} ");
sb.Append("}");
return sb.ToString();
}
}

public static class TextExtensions
{
public static string ToBinaryString(this uint value, int width = sizeof(uint) * 8)
{
var stack = new Stack<char>();

while (value > 0)
{
stack.Push(value % 2 == 0 ? '0' : '1');
value /= 2;
}

while (stack.Count < width)
stack.Push('0');

return string.Join("", stack);
}
}``````

Last edited:
• DANILIN

#### Skydiver

Staff member
The reason for using the `Item` and `Configuration` classes is because it's a reaction to this: "If you are using parallel arrays to keep track of related items, this is a code smell that those related items should live in a data structure."

I was about to do the same thing for the cases when you convert the bits of an integer into a string, and then have a parallel array of 0's and 1's based on the string, and then that array was used to add up the weights and costs. As I was refactoring though, I realized that the string and the array of 0's and 1's was just transient. What was really happening was that you were only adding in the weight and cost for the corresponding item only if the bit value was 1. Hence the lines 64-76 in my code.

• DANILIN

#### DANILIN

##### Active member
Now my design visually right observer of margins

1 is added to left and investigated
111 110 101 100

Right part is taken from them
11 10 01 00
with all zeros

Where number of registers is equal to number of items

If you examine everything up to 0
then we'll get to options 1 and 0
what is less than number of items

Conclusion: now ciphers always correspond to subjects
and there is an implementation in Excel just a table

C#:
``````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]);
}
}
}``````

Last edited:

#### Skydiver

Staff member
Ah I see:
C#:
``````n = 2

all = 2**(n+1)
all = 2**(2+1)
all == 2**3
all == 8

for (list = 8-1; list > (8-1)/2; list--) { ... }
for (list = 7; list > 7/2; list--) { ... }
for (list = 7; list > 3; list--) { ... }``````

That means that `dec` will on have the following values going from through lines 41-50:
C#:
``````decimal binary bin-string-variable
7       111    "111"
6       110    "110"
5       101    "101"
4       100    "100"``````

And then line 51 lops off the leading '1` from the strings.

But then lines 53-58 only looks at the two letters of the `bin` string variable.

So it looks like you are wasting both memory and CPU computing from 7 down to 4. You could have simply had:
C#:
``````int totalPermutations = 1 << (n-1);    // or (int)Math.Pow(2, n);
for (int list = 0; list < totalPermutations; list++) { ... }``````
C#:
``````decimal binary bin-string-variable
0       00     "00"
1       01     "01"
2       10     "10"
3       11     "11"``````
Line 51 can be deleted because there is no need to lop off the first letter.

Last edited:
• DANILIN

#### Skydiver

Staff member
You don't really need to binary to string, then string to integer conversion. Not only are those extra operations, recall that following 2 multiplications that you are doing against that integer is more expensive than a compare and branch. As I recall, multiplication used to be 10 to 20 times slower than a compare and branch.

Add on the fact that you are writing code in C#. Unless you do micro optimizations (and dramatically hurt the readability of your code), every array access in C# has a bounds check performed. This is different from C/C++ where array accesses only come at the cost of slow memory retrieval if the array index is not in the CPU cache. For C# you have at 2 branch and compare operations before the memory retrieval.

To get around this, you would need to use CPU vector operations in C#. Although supported on on CPU platforms by using some C# libraries, these vector operations are kind of clumsy to use.

• DANILIN

#### DANILIN

##### Active member
I have it converted from binary to a number 0 or 1
in current calculation only 1 character

C#:
``jack[k]=Convert.ToInt32(bin[list].Substring(k,1));``

corresponding to number of list item
what is real to use even on paper by manually

#### Skydiver

Staff member
Yes, you have to pull out the binary digits, but there is no need to pull out the binary digit, stick it into a string, and then pull out of a string, and put into an array, and then finally pull out of the array and multiply with the corresponding item to determine whether to add the item into the knapsack or not.

You can just pull out the digit and check if 0 or 1. If 1, then add the item to the knapsack.

The issue is that you are trying to cut down the number of comparisons by hiding them into your vector multiplication of the array. What you are not realizing is that there are at least 1 or more comparisons underlying the multiplication. There at least two comparisons to access that vector of 0's and 1's. There are at least 3 comparisons to perform that substring operation to pull out a single character. There are at least 3 comparisons to put characters into the string.

• DANILIN

#### DANILIN

##### Active member
"you are trying to cut down the number of comparisons
by hiding them into your vector multiplication of the array"

absolutely everything is compared
and only what is less than or equal to Knapsack is printed

C#:
``````if (amount[list]<= Inside) // current mass < Knapsack
{
Console.WriteLine("{0} {1} {2} {3}", Inside, amount[list], quality[list], bin[list]);
}``````

removing condition: it will print everything

#### Skydiver

Staff member
But what's wrong is that you are only counting the number of times that `amout[list] <= Inside` is called. You are not taking into account the new comparisons that you have taken on like `k < n` in your for loop, or the implicit comparisons performed by the CPU when you do `mass[k]*jack[k]` to do the multiplication, or the implicit comparisons performed by the CPU when you access an array element to get `mass[k]`, `jack[k], or [icode]bin[i]`. You are not counting the comparison `dec > 0` by your while loop. You are not counting the implicit comparison. You are not counting the implicit comparisons done when appending characters to `bin[list]`.

Or let me put it this way. Traditionally, the knapsack algorithm efficiency is just measured by the number of comparisons, because the bottleneck is the comparison highlighted below in the pseudo code:
C#:
``````for all combinations of items do
let knapsack be empty
for each item in a combination do
if knapsack is overweight
break
if knapsack is not overweight
consider this a potential valid solution``````
The reason why the comparison is considered the bottleneck is because branches are expensive, as well as, there is a direct correlation between the number of comparisons and the number of times items are added into the backpack. `O(n!) + O(n!) = O(2n!) = O(n!)`. First `O(n!)` for the addition, and then the second for the comparison.

What you are doing is now:
C#:
``````for all combinations of items do
let knapsack be empty
for each item in a combination do
if knapsack is not overweight
consider this a potential valid solution``````

The traditional approach is to put the knapsack on the ground, put in an item into the knapsack, and then pick it up to see if it breaks. If not, put the knapsack back on the ground, put in another item, and then pick it up again to see if it breaks. Repeat until you either break the knapsack, or you got all the item combinations you wanted into the knapsack.

Your approach is to put the knapsack on the ground, put all items of the combination into the knapsack, then pick it up to see if it breaks.

Yes, you reduced the number of times you picked up the backpack. But you didn't reduce the number of times you pick up items from the ground and put it into the knapsack. (line 4 of both chunks of pseudo code above). In fact, my gut feel is that you've actually increased the number of times you add items into the knapsack.

• DANILIN

#### DANILIN

##### Active member
my program from topic: 7 elements
online rextester.com/YRFA61366

by excluding of condition

C#:
``//if (amount[list]<= Inside) // current mass < Knapsack``

we start and see column of solutions

to avoid adding variables: I highlight and copy results
& I paste it into notepad and Ctrl+G & I see 128 lines

2^7 = 128
7! = 5040

7!/(2^7) = 39,375

Total: in my algorithm, factorial does not occur
and number of operations is a multiple of less

Plus I found a classic solution of 20 elements
where the answer is: 396 kg & 1030 kg

and my algorithm solved it too :
396 1030 11111010001000011111

jdoodle.com/ia/rSn

Last edited:

#### Skydiver

Staff member
But that's just comparisons. Start counting how many times you loop around on for lines 37-41 and lines 47-52.

• DANILIN

Replies
3
Views
264
Replies
29
Views
1K
Replies
0
Views
457
Replies
1
Views
319
Replies
20
Views
606