Ich habe diesen Code gefunden, um das Knapsack-Problem mit Hilfe des Brute-Force-Mechanismus zu lösen (dieser dient hauptsächlich dem Lernen, daher ist es nicht erforderlich, auf Dynamik hinzuweisen, umso effizienter). Ich habe den Code zum Laufen gebracht und verstehe das meiste davon. DIE MEISTEN. Hier ist die Frage:

Ich habe festgestellt, dass diese beiden Bedingungen keine Ahnung haben, wie sie funktionieren und warum sie im Code enthalten sind. Ich weiß, dass sie von entscheidender Bedeutung sind, da der Algorithmus aufgrund von Änderungen zu falschen Ergebnissen geführt hat:

// if bit not included then skip
if (((i >> j) & 1) != 1) continue;

// if bit match then add
if (((bestPosition >> j) & 1) == 1)
{
    include.Add(Items[j]);
}

Hier ist die ganze Klasse und wie ich sie von main aus rufe:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace KnapSack2
{
    class BruteForce
    {
        public double Capacity { get; set; }
        public Item[] Items { get; set; }

        public Data Run()
        {
            int bestValue = 0;
            int bestPosition = 0;
            int size = Items.Length;

            var permutations = (long)Math.Pow(2,size);

            for (int i = 0; i<permutations; i++)
            {
                int total = 0;
                int weight = 0;
                for (int j = 0; j<size; j++)
                {
                    //jeżeli bit "not included" to omin"
                    if(((i>>j)&1)!=1)
                        continue;
                    total += Items[j].v;
                    weight += Items[j].w;
                }
                if (weight <= Capacity && total>bestValue)
                {
                    bestPosition = i;
                    bestValue = total;
                }
            }
            var include = new List<Item>();
            for (int j = 0; j<size; j++)
            {
                // jeżeli bit pasuje, wtedy dodaj
                if (((bestPosition>>j) & 1)==1)
                    include.Add(Items[j]);
            }
            return new Data { BestValue = bestValue, Include = include };

        }//End of Run


    }
}

ufrufen in main

var ks = new BruteForce
{
    Capacity = MaxWeight,
    Items = items.ToArray()
};

Data result = ks.Run();

Item-Klasse ist nur ein einfaches Objekt, das Wert, Gewicht und ID enthält