Knapsack 0-1 C# binary & rosettacode & WE

DANILIN

Active member
Joined
Oct 19, 2018
Messages
39
Programming Experience
10+
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

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

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


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
Joined
Apr 6, 2019
Messages
5,469
Location
Chesapeake, VA
Programming Experience
10+
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

Active member
Joined
Oct 19, 2018
Messages
39
Programming Experience
10+
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
Joined
Apr 6, 2019
Messages
5,469
Location
Chesapeake, VA
Programming Experience
10+
If you have to comment a variable, that is a code smell that you are not using meaningful variable names.
 
Last edited:

Skydiver

Staff member
Joined
Apr 6, 2019
Messages
5,469
Location
Chesapeake, VA
Programming Experience
10+
Why do you only check half of the combinations (e.g. h: a-1..(a-1)/2)?
 

DANILIN

Active member
Joined
Oct 19, 2018
Messages
39
Programming Experience
10+
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
Joined
Apr 6, 2019
Messages
5,469
Location
Chesapeake, VA
Programming Experience
10+
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

Staff member
Joined
Apr 6, 2019
Messages
5,469
Location
Chesapeake, VA
Programming Experience
10+
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));
        }

        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);
    }
}
 
Last edited:

Skydiver

Staff member
Joined
Apr 6, 2019
Messages
5,469
Location
Chesapeake, VA
Programming Experience
10+
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

Active member
Joined
Oct 19, 2018
Messages
39
Programming Experience
10+
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


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:
Solution

Skydiver

Staff member
Joined
Apr 6, 2019
Messages
5,469
Location
Chesapeake, VA
Programming Experience
10+
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++) { ... }
which will then lead to:
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:

Skydiver

Staff member
Joined
Apr 6, 2019
Messages
5,469
Location
Chesapeake, VA
Programming Experience
10+
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

Active member
Joined
Oct 19, 2018
Messages
39
Programming Experience
10+
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
Joined
Apr 6, 2019
Messages
5,469
Location
Chesapeake, VA
Programming Experience
10+
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

Active member
Joined
Oct 19, 2018
Messages
39
Programming Experience
10+
"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
Joined
Apr 6, 2019
Messages
5,469
Location
Chesapeake, VA
Programming Experience
10+
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
        add item to knapsack
        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
        add item to knapsack
    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

Active member
Joined
Oct 19, 2018
Messages
39
Programming Experience
10+
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
Joined
Apr 6, 2019
Messages
5,469
Location
Chesapeake, VA
Programming Experience
10+
But that's just comparisons. Start counting how many times you loop around on for lines 37-41 and lines 47-52.
 
Top Bottom