Я нашел этот код для решения проблемы Knapsack с использованием механизма грубой силы (это в основном для обучения, поэтому нет необходимости указывать динамику более эффективно). Я получил код для работы и понимаю большую часть этого. БОЛЬШИНСТВО. Здесь вопрос:
Я заметил эти два условных выражения, что я понятия не имею, как они работают и почему они находятся в коде - я знаю, что они жизненно важны, поскольку любые изменения, которые я сделал, заставили алгоритм произвести неправильные результаты:
// 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]);
}
Здесь весь класс и способ, которым я вызываю его из main:
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
}
}
Вызов основного
var ks = new BruteForce
{
Capacity = MaxWeight,
Items = items.ToArray()
};
Data result = ks.Run();
Класс элемента - это просто значение объекта, вес и идентификатор
