背包-蛮力算法 [英] Knapsack - brute force algorithm
问题描述
我发现此代码使用蛮力机制解决背包问题（这主要是为了学习，因此无需指出动态更有效）。我得到了可以工作的代码，并且了解了大部分代码。最。问题是：
I have found this code to solve Knapsack Problem using brute force mechanism (this is mostly for learning, so no need to point out dynamic is more efficient). I got the code to work, and understand most of it. MOST. Here's the question:
我注意到这两个条件，我不知道它们如何工作以及它们为什么在代码中-我知道它们至关重要，因为我所做的任何更改都会导致算法产生错误的结果：
I've noticed those two conditionals, that I have no idea how they work and why they are in the code - I know they are vital, since any changes I've made caused the algorithm to produce wrong results:
// 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调出来的方式：
Here's the whole class, and the way I'm calling it out from 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
Item class is just a simple object holding value, weight and ID
推荐答案
此& 是按位与AND
按位与运算符将其第一个操作数的每个位与第二个操作数的
对应位进行比较。如果两个位都为1，则将
的相应结果位设置为1。否则，将相应的
的结果位设置为0。
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.
话虽如此，让我们采用以下表达式
That being said, let's take the following expression
if (((i >> j) & 1) != 1) continue;
并尝试理解它。
最初，此 i>> j 会将 i 的位右移 j 个位置。
Initially, this i >> j will shift right the bits of i by j positions.
例如，让我们进行以下分配：
For instance, let we have the following assignment:
int number = 5;
数字的二进制表示形式是：
The binary representation of number is:
0000 0000 0000 0000 0000 0000 0000 0101
如果我们将新整数定义为：
If we define a new integer as:
int shiftNumbersBitByOne = a >> 1;
然后 shiftNumbersBitByOne 的二进制表示形式是：
Then binary representation of shiftNumbersBitByOne would be:
0000 0000 0000 0000 0000 0000 0000 0010
然后根据此运算和1的结果，应用按位AND运算符。
Then on the result of this operation and 1, we apply the bitwise AND operator.
此运算符到底是什么？
What does exactly this operator ?
尽管定义很明确，但下面的示例将使它更加清晰。
Despite the fact that the definition is clear, an example will make it more clear.
让我们使用二进制数 a 和 b ，则 a& b 的结果如下：
Let that we have the binary numbers a and b, then the result of a&b is the following:
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
That being said, in this operation (i >> j) & 1 we apply the bitwise-AND operator between the result of i >> j and the binary representation of 1
0000 0000 0000 0000 0000 0000 0000 0001
当
（i>> j）的结果时& 1是1吗？
如果且仅当 i>>的最后一位j 为1。
更新
以上我们讨论了如何部分-我不知道它们如何工作。现在我们要解决为什么部分-为什么在代码中。
Above we addressed the how part -I have no idea how they work. Now we will address the why part -why they are in the code.
让我们定义问题，背包问题。根据维基百科
Let's define our problem, the Knapsack problem. According to 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 访问。建议您将其分别重命名为值和权重，以使代码更有意义。
Furthermore, based on your code, we can deduce that each item has a value and a weight that can be accessed as item.v and item.w respectively. I suggest you rename this to value and weight respectively, in order your code to be more meaningful.
显然，此 int大小= Items.Length ; 是可用项目的数量。
Apparently, this int size = Items.Length; is the number of the available items.
部分开始的全部要点：
var permutations = (long)Math.Pow(2,size);
排列是什么？ 排列代表什么？
What is the permutations? What does permutations represent?
在回答这个问题之前，让我们考虑一下如何表示项目集合将在最终解决方案中使用。我认为只要我们有n个项目，就可以用n位数字表示。那怎么可能？如果n位编号中的每个位都引用n个项目之一，则很明显我们可以这样做。如果第n个 项不包含在最终解决方案中，则第n个 位的值为0。如果将其包括在内，则其值为1。
Before we answer this question, let's think about how we can represent which items of the items collection will be used in the final solution. I argue that we can represent this with a n-bit number provided that we have n items. How is that possible? If each bit in the n-bit number refers to one of the n-items, it is pretty evident we can do so. The value of the n-th bit would be 0, if the n-th item will not be included in the final solution. While it's value would be 1, if it will be included.
很明显，排列代表什么。 它代表最终解决方案中所有可能的项目组合。这很清楚，因为每个位可以有2个值（0或1）。考虑到我们有n位，则可能的组合数为2 ^ n。
That being said is pretty clear what permutations represents. It represents all the possible combinations of the items in the final solution. This is clear, because each bit can have 2 values, either 0 or 1. Given that we have n-bits, the number of the possible combinations is 2^n.
实际上，由于这个原因，该算法是蛮力算法（我们进行了详尽的搜索）。我们访问所有可能的组合以找到最佳组合。在以下循环中：
Actually, for this reason this algorithm is a brute force algorithm (we do an exhaustive search). We visit all the possible combinations to find the best one. In the following loop:
for (int i = 0; i<permutations; i++)
{
// ...
}
您可以遍历所有可能的组合。
you loop through all the possible combinations.
然后foreach组合，您将遍历项目集合：
Then foreach combination, you loop through the items collection:
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;
}
现在，如果重量小于限制值，并且的总值大于当前的最佳总和，我们选择此组合作为当前的最佳总和：
Now if the weight is less than the limit value and the total value is greater than the best current total value, we pick this combination as the current best:
bestPosition = i;
bestValue = total;
最后，遍历所有可用组合，我们将提供最好的组合。
At the end, having looped through all the available combinations, we will have the best one.
找到了最佳组合，我们必须遍历所有项目以查看其中的哪些组合。
Having found the best combination, we have to loop through the items to see which of them are included in this combination.
// 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]);
}
这篇关于背包-蛮力算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
