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]

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:

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:

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]

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

by excluding of condition

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

 

[Skydiver]

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