背包 - 蛮力算法

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

这是整个班级,以及我从主要方式调用它的方式:

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类只是一个包含值,权重和ID的简单对象

Answer 1

这&是bitwise-AND

按位AND运算符将其第一个操作数的每个位与其第二个操作数的相应位进行比较.如果两个位均为1,则相应的结果位设置为1.否则,相应的结果位设置为0.

虽然这>>是右移运营商

右移运算符(>>)将其第一个操作数右移第二个操作数指定的位数.

话虽这么说,让我们采取以下表达式

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运算符.

这个运营商究竟是什么？

尽管定义很明确,但一个例子将使其更加清晰.

让我们有二进制数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的二进制表示之间应用按位AND运算符

0000 0000 0000 0000 0000 0000 0000 0001

当结果(i >> j) & 1是1？

当且仅当最后一位数i >> j为1时才会发生这种情况.

更新

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

让我们来定义我们的问题,即背包问题.根据维基百科

背包问题或背包问题是组合优化中的一个问题:给定一组具有质量和值的项目,确定要包含在集合中的每个项目的数量,以使总重量小于或等于a给定限制,总值尽可能大.

根据以上所述,这是直截了当的

// 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的值为第位将是0,如果在n 个项目不会被包括在最终的溶液中.虽然它的价值是1,但它是否包括在内.

所说的很清楚排列代表什么.它代表最终解决方案中项目的所有可能组合.这很清楚,因为每个位可以有2个值,0或1.鉴于我们有n位,可能组合的数量是2 ^ n.

实际上,由于这个原因,这个算法是一个强力算法(我们做了详尽的搜索).我们访问所有可能的组合以找到最佳组合.在以下循环中:

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

你循环所有可能的组合.

然后foreach组合,你循环遍历项集合:

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

当且仅当j-th位i为零时才为真; 条件

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

当且仅当j-th位bestPosition为1 时才为真.关于更大的图片,显然实现用于int对一组项进行建模,其中j当且仅当j-th项包含在集中时才设置-th位; 因此,会员资格测试可以通过比特检查来完成.该实现枚举项的所有子集(int用于表示它们)以执行穷举搜索.

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