背包-蛮力算法

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();

Item class 只是一个简单的对象，包含值、重量和 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，我们应用按位AND运算符。

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 访问。我建议您将其分别重命名为 value 和 weight，以使您的代码更有意义。

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

为什么部分从这里开始的全部要点:

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

什么是permutations？ permutations代表什么？

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

话虽这么说，但排列代表什么已经很清楚了。 代表最终解中所有可能的项目组合。这很清楚，因为每个位可以有 2 个值，0 或 1。鉴于我们有 n 位，可能的组合数是 2^n.

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

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

你遍历所有可能的组合。

然后对于每个组合，循环遍历项目集合：

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

Answer 2

显然，有问题的代码部分是检查是否设置了某个位，如注释所示。条件

((i >> j) & 1) != 1

当且仅当 i 的第 j 位为零时，

为真；条件

((bestPosition >> j) & 1) == 1

当且仅当 bestPosition 的第 j 位为一时，

为真。关于更大的图景，显然该实现使用 int 来模拟一组项目，其中第 j 位设置当且仅当第 j 项目包含在放;因此，成员资格测试可以通过位检查来完成。该实现枚举项目的所有子集（使用 int 来表示它们）以执行详尽搜索。

请注意，集合的 Delphi 实现使用相同的方法，但对客户端代码隐藏了位索引。

背包-蛮力算法

Knapsack - brute force algorithm

c#

algorithm

brute-force

knapsack-problem