Knapsack 0-1 C# binary & rosettacode & WE

[DANILIN]

Knapsack 0-1 C# binary & rosettacode & WE

Classic Knapsack problem is solved in many ways

Contents: Knapsack problem - Rosetta Code
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

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:

# 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

 

[Skydiver]

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]

I indented my code in indent style
and commented variable names

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

 

[Skydiver]

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

 

[Skydiver]

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

 

[DANILIN]

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

otherwise number of characters in cipher will decrease

plus meaningful variable names

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]

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?

 

[Skydiver]

Here's my re-write of the code, but I go through the entire range of values instead of just the top half:

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

        IEnumerable<Configuration> GenerateConfigurations(IReadOnlyList<Item> items)
        {
            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;

    public Configuration(uint configurationNumber, IReadOnlyList<Item> items)
    {
        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);
    }
}

 

[Skydiver]

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]

Now my design visually right observer of margins

About quantity: for n=2
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

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

 

[Skydiver]

Ah I see:

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:

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:

int totalPermutations = 1 << (n-1);    // or (int)Math.Pow(2, n);
for (int list = 0; list < totalPermutations; list++) { ... }

which will then lead to:

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.

 

[Skydiver]

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]

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

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]

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]

"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

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