背包问题 - 枚举算法

Question

背包问题 - 枚举算法

17

我发现这段代码使用暴力机制来解决背包问题（主要是为了学习，所以不必指出动态规划更有效）。我使代码工作，并理解了其中大部分内容。但是，这里有个问题：

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

// 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。

- Bartosz Cieszewski

5

看起来你的问题更适合于代码审查网站，因为它正在工作且没有出现错误。 - Andrey Korneyev

5

这个代码：((i >> j) & 1) != 1 确切地执行了它前面的注释所说的：它将检查在 i 的二进制表示中，从右往左数第 j 位（从0开始计算）是否为0。它通过将 i 向右移动 j 位来移除 i 的最后 j 个比特位，并与 ..000001 进行按位与操作 & ，然后查看结果是否为 1，以此来判断该位是否为0。 - Random Dev

我可以补充一下，这是使用“二进制计数器”技术来生成所有组合的方法，因此我们必须使用位运算。 - Ilia Maskov

1

@AndyKorneyev 我不认为Code Review接受“向我解释其他人编写的代码”的问题。它更多关于“我编写了这个代码，如何让它更好？” - CodesInChaos

2个回答

9

显然，涉及的代码部分是检查特定位是否被设置，如注释所示。条件语句

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

只有当i的第j位是0时，条件才成立。

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

只有当bestPosition的第j位为1时，才会返回true。就整体而言，该实现使用int来模拟一组项目，其中第j位设置为1，当且仅当第j个项目包含在集合中；因此，可以通过位检查进行成员资格测试。该实现枚举所有项目的子集（使用int来表示它们）以执行详尽搜索。

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

- Codor

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Christos · Accepted Answer

这个 & 是按位与运算符

按位与运算符将第一个操作数的每个位与第二个操作数的相应位进行比较。如果两个位都是1，则相应的结果位设为1。否则，相应的结果位设为0。

而这个 >> 则是右移位运算符

右移位运算符（>>）将其第一个操作数向右移动由其第二个操作数指定的位数。

话虽如此，我们来看下面的表达式：

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

尝试理解它。

最初，这个 i >> j 会将 i 的位向右移动 j 位。

例如，假设我们有以下赋值：

int number = 5;

< p > number 的二进制表示为：

0000 0000 0000 0000 0000 0000 0000 0101

如果我们定义一个新的整数：

int shiftNumbersBitByOne = a >> 1;

那么shiftNumbersBitByOne的二进制表示将是：

0000 0000 0000 0000 0000 0000 0000 0010

然后我们对这个操作和1的结果应用按位与运算符。

这个运算符到底是什么意思？

虽然定义很清楚，但一个例子能让它更清晰易懂。

假设我们有二进制数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

如果 i >> j 的最后一位是 1，那么 (i >> j) & 1 的结果就是 1。

更新：

我们刚才解决了它们是如何运作的这个问题，现在我们来解决它们为什么出现在代码中这个问题。

让我们来定义我们的问题，背包问题。根据维基百科：

背包问题也称为背包，是组合优化中的一个问题。给定一组物品，每种物品都有自己的重量和价值，在限定的总重量内，选择其中若干个（也即每种物品可以选0个或1个），设计选择方案使得物品总价值最大。

根据上述内容，很明显：

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

什么是排列？排列代表什么意思？

在回答这个问题之前，让我们考虑如何表示哪些项目将用于最终解决方案。我认为，如果有n个项目，我们可以用一个n位数字来表示。这是怎么可能的呢？如果n位数字中的每一位都指向n个项目中的一个，那么很明显我们就可以这样做。如果第n位对应的项目不会包含在最终解决方案中，那么它的值将为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]);
}