背包 – 蛮力算法
我发现这个代码使用powershell机制来解决背包问题（这主要是为了学习，所以不需要指出动态更有效）。 我让代码工作，并了解其中的大部分内容。 最。 这是问题：
我注意到这两个条件，我不知道它们是如何工作的以及为什么它们在代码中 – 我知道它们是至关重要的，因为我所做的任何改变都会导致算法产生错误的结果：
// 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级，以及我从主要方式调用它的方式：
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>j)&1)!=1) continue; total += Items[j].v; weight += Items[j].w; } if (weight bestValue) { bestPosition = i; bestValue = total; } } var include = new List(); for (int j = 0; j>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的简单对象
这是& bitwise-AND
按位AND运算符将其第一个操作数的每个位与其第二个操作数的相应位进行比较。 如果两个位均为1，则相应的结果位设置为1.否则，相应的结果位设置为0。
虽然这个>>是右移运营商
右移运算符（>>）将其第一个操作数右移第二个操作数指定的位数。
话虽如此，让我们采取以下表达方式
if (((i >> j) & 1) != 1) continue;
并尝试理解它。
最初，这个i >> j会将i >> j位移到j位置。
例如，我们有以下任务：
int number = 5;
数字的二进制表示是：
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的二进制表示之间应用bitwise-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项不包括在最终解决方案中，则第n位的值将为0。 虽然它的价值是1，但如果它将被包括在内。
所说的很清楚排列代表什么。 它代表最终解决方案中项目的所有可能组合 。 这很清楚，因为每个位可以有2个值，0或1.鉴于我们有n位，可能组合的数量是2 ^ n。
实际上，由于这个原因，这个算法是一个powershell算法（我们做了详尽的搜索）。 我们访问所有可能的组合以找到最佳组合。 在以下循环中：
for (int i = 0; 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- (); // We loop through all the available items for (int j = 0; j
>j) & 1)==1) include.Add(Items[j]); }
显然，所讨论的代码部分是对某个位被设置的检查，如注释所示。 条件
((i >> j) & 1) != 1
当且仅当j第j位为零时才为真; 条件
((bestPosition >> j) & 1) == 1
当且仅当bestPosition第j位为1 bestPosition为真。 关于更大的图片，显然实现使用int来模拟一组项目，其中第j位设置当且仅当第j项包含在集合中时; 因此，可以通过比特检查来完成成员资格测试。 该实现枚举项的所有子集（使用int来表示它们）以执行穷举搜索。
请注意，集合的Delphi实现使用相同的方法，但隐藏了客户端代码的位索引。