c# - 背包-蛮力算法

Question

我发现此代码使用蛮力机制解决背包问题(这主要是为了学习，因此无需指出动态更有效)。我得到了可以工作的代码，并且了解了大部分代码。最多。这是问题:

我注意到这两个条件，我不知道它们如何工作以及为什么在代码中-我知道它们至关重要，因为我进行的任何更改都会导致算法产生错误的结果:

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

这是整个类(class)，以及我从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();

物品类别只是一个简单的对象，包含值，重量和ID

Answer 1

此&是bitwise-AND

The bitwise-AND operator compares each bit of its first operand to the corresponding bit of its second operand. If both bits are 1, the corresponding result bit is set to 1. Otherwise, the corresponding result bit is set to 0.

虽然此 >>是右移运算符

The right-shift operator (>>) shifts its first operand right by the number of bits specified by its second operand.

话虽如此，让我们采用以下表达式

if (((i >> j) & 1) != 1) continue;

并尝试了解它。

最初，此 i >> j将 i的位置右移 j的位置。

例如，让我们进行以下分配:

int number = 5;

number的二进制表示为:

0000 0000 0000 0000 0000 0000 0000 0101

如果我们将新整数定义为:

int shiftNumbersBitByOne = a >> 1;

然后 shiftNumbersBitByOne的二进制表示为:

0000 0000 0000 0000 0000 0000 0000 0010

然后，根据此运算和1的结果，应用按位与运算符。

What does exactly this operator ?

尽管定义很明确，但举个例子可以使它更清晰。

假设我们有二进制数 a和 b，那么 a&b的结果如下:

a =     0001 0100 1010 0001 1000 1010 1101 0011
b =     0010 1100 1111 0111 0011 1010 1011 0111
a & b = 0000 0100 1010 0001 0000 1010 1001 0011

就是说，在此操作 (i >> j) & 1中，我们在 i >> j的结果与1的二进制表示形式之间应用按位与运算符

0000 0000 0000 0000 0000 0000 0000 0001

When the result of (i >> j) & 1 would be 1?

仅当 i >> j的最后一位为1时，才会发生这种情况。

更新

上面我们讨论了 如何部分-我不知道它们如何工作。现在，我们将解决 和部分的原因-为什么它们在代码中。

让我们定义问题，背包问题。根据 wikipedia

The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a mass and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

根据以上所述，很直接

// This is the total weight limit.
public double Capacity { get; set; }

和

// This is an array with all the given items.
public Item[] Items { get; set; }

此外，根据您的代码，我们可以推断出每个项目都有一个值和权重，可以分别通过 item.v和 item.w进行访问。我建议您将其分别重命名为值和权重，以使代码更有意义。

显然，此 int size = Items.Length;是可用项目的数量。

部分开始的全部要点:

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

什么是 permutations？ permutations代表什么？

在回答这个问题之前，让我们考虑一下如何表示项目集合中的哪些项目将在最终解决方案中使用。我认为只要我们有n个项目，就可以用n位数字表示。那怎么可能？如果n位数字中的每个位都引用n个项之一，则很明显我们可以这样做。如果最终解决方案中不包含第n个项目，则第n个位的值为0。如果将其包括在内，则其值为1。

话虽如此，排列代表什么。 它代表最终解决方案中所有项目的可能组合。这很清楚，因为每个位可以有2个值(0或1)。假定我们有n位，则可能的组合数为2 ^ n。

实际上，由于这个原因，该算法是 蛮力算法(我们进行了详尽的搜索)。我们访问所有可能的组合以找到最佳组合。在以下循环中:

for (int i = 0; i<permutations; i++)
{ 
    // ...
}

您遍历所有可能的组合。

然后进行foreach组合，循环遍历items集合:

for (int j = 0; j < size; j++)
{
    // Here you check if the item in position j
    // is included in the current combination.
    // If it is not, you go to the next value of the loop's variable
    // and you make the same check.
    if(((i>>j)&1)!=1)
        continue;

    // The j-th item is included in the current combination. 
    // Hence we add it's
    // value to the total value accumulator and it's weight to 
    // the total weight accumulator.
    total += Items[j].v;
    weight += Items[j].w;
}

现在，如果 weight小于极限值 和，则总值大于当前的最佳总值，我们将此组合作为当前的最佳值:

bestPosition = i;
bestValue = total;

最后，遍历所有可用组合，我们将为您提供最佳组合。

找到最佳组合后，我们必须遍历各个项目以查看其中的哪些组合。

// The include is a list that will hold the items of the best combination.
var include = new List<Item>();

// We loop through all the available items
for (int j = 0; j<size; j++)
{
    // If the items is included in the best combination,
    // add this item to the include list.
    if (((bestPosition>>j) & 1)==1)
        include.Add(Items[j]);
}