65.9K
CodeProject 正在变化。 阅读更多。
Home

背包问题（位运算）

Kerneels Roos
starIconstarIconstarIconstarIconstarIcon

5.00/5 (2投票s)

2016年10月17日

Apache

7分钟阅读

viewsIcon

15184

在本系列的第一个帖子中，我将为这个我于2015年设计的著名问题的1⁄0或二进制版本提供解决方案。

计算机科学中的一个有趣问题，背包问题已经被研究了一个多世纪，根据维基百科，它似乎相当受欢迎——就像这类事物一样。在本系列的第一个帖子中，我将为这个我于2015年设计的著名问题的1⁄0或二进制版本提供解决方案。

当我第一次读到这个问题陈述时，我就被它深深吸引了。它在任何需要最优资源分配的方面的应用都非常清晰，我的大脑开始痴迷于如何高效地解决这个问题。对于这样一个经过深入研究的问题，当然已经开发了许多算法，但由于这个问题是一个测试，我没有查阅任何资料，而是一旦有了想法就开始编写解决方案。

完整的解决方案在此GitHub上可用，但我们鼓励您从本文复制代码并粘贴到您自己的项目中，以便逐步理解整个过程。

这是什么？

0/1或二进制变体非常简单。给定一组物品，每件物品都有重量和价值，确定最优的物品选择，使得所有物品的总重量不超过某个限制，同时最大化所有物品的总价值。

名称中的0/1或二进制部分源于每个物品只能选择一次的限制。“背包”这个名字指的是一个虚构的背包或袋子，它只能承受给定的重量。这个问题的复杂性在于所有可能的物品选择的指数级爆炸。

具体示例

假设我们有以下15件物品

数字 名称 重量（克） 值
0 map 90 150
1 指南针 130 35
2 水 1530 300
3 金条 3000 130
4 三明治 500 160
5 葡萄糖 150 60
6 锡 680 45
7 香蕉 270 60
8 苹果 390 40
9 奶酪 230 30
10 啤酒 620 10
11 防晒霜 110 70
12 相机 320 30
13 T恤 240 15
14 裤子 480 10

我们的背包最多只能装4公斤或4000克，但我们希望选择具有最高可能价值的物品（或库存）。

有多少种可能的库存？

考虑到我们有n件物品可供选择，每件物品都有重量w和价值v，我们注意到

  1. 我们绝不会选择零件物品。
  2. 我们可以选择包含某件物品，也可以不包含。

我们尝试了一个计算选择数量的公式：c = 2^n - 1。2^n是因为每件物品都可以被选中或不被选中，而- 1是为了排除不选择任何物品的情况。

让我们看看它对一件物品的情况：c = 2^1 - 1 = 2 - 1 = 1，这很明显，因为只有一件物品时，您只有一种选择——这可以作为我们的基本情况，所以对于n = 1，公式成立。现在我们考虑n + 1，即2件物品：c = 2^2 - 1 = 4 - 1 = 3，这是有道理的，因为您可以选择其中一件物品或两件物品，所以对于n + 1，公式也成立。因此，通过数学归纳法，我们的公式得到了证明，尽管我们凭直觉就知道它是正确的。

使用我们的公式，我们得出有c = 2^15 - 1 = 32768 - 1 = 32767种可能的库存。这个数字在计算机术语中可以忽略不计，但对于手动计算来说已经太大了。

暴力破解解决方案

由于我们当前的情况非常小，我们将简单地进行暴力搜索，以找到满足4000克重量限制的最佳库存（如果有的话）。

任何库存最多只能包含15件物品，因此我们将用位掩码来表示任意库存，其中每个位将代表一个特定的物品，0表示未选择该物品，1表示选择了该物品。

位掩码将驱动一个计算函数来确定给定库存的总重量和总价值。现在，考虑所有可能的库存被简化为迭代数字1到32767种可能的选项，每次计算重量和价值的总和，并保留那些满足重量限制的库存。

复杂性

使用我们的公式，我们可以说我们的解决方案将具有O(2^n - 1)的时间复杂度，同样，最坏情况下的空间复杂度也是O(2^n - 1)。

实现

物品和库存类

查看物品列表，我们意识到我们需要一个类来表示单个物品（我们称之为class Belonging），以及所有物品的集合（class Inventory）。

namespace Knapsack
{
public class Belonging
	{
		public byte Number { get; set; }
		public string Name { get; set; }
		public int GramsWeight { get; set; }
		public int Value { get; set; }
	}

	public class Inventory
	{
		public static List<Belonging> AllGear { get; set; }

		public uint Gear { get; set; }
	}
}

物品类的函数

既然我们已经解决了数据需求，让我们为每个类添加一些功能。以真正的[测试驱动开发][TDD]风格，我们首先为每个函数创建单元测试，然后实现它们。

我们将所有测试类包装在一个通用的TestKnapsack类中，我们可以在需要时执行设置和清理操作。

namespace Knapsack
{
	[TestClass]
	public class TestKnapsack
	{
		[TestClass]
		public class TestBelonging : TestKnapsack
		{
			[TestMethod]
			public void ShouldAddRemoveAndConfirmItIsInGear()
			{
				uint gear = 0; // empty set of gear
				var testBelonging = new Belonging { Number = 0, Name = "map", GramsWeight = 90, Value = 150 };

				Assert.IsFalse(testBelonging.IsInGear(gear));
				uint gearAfterAdd = testBelonging.AddToGear(gear);
				Assert.IsFalse(testBelonging.IsInGear(gear));
				Assert.IsTrue(testBelonging.IsInGear(gearAfterAdd));
				Assert.AreNotEqual(gearAfterAdd, gear);

				uint gearAfterRemove= testBelonging.RemoveFromGear(gearAfterAdd);
				Assert.AreEqual(gearAfterRemove, gear);
				Assert.IsFalse(testBelonging.IsInGear(gearAfterRemove));
			}
		}
	}
}

回到我们的Belonging类，让我们实现我们在单元测试类中描述的方法。

我们将大量使用位运算符

  • <<和>>：位移，将数字中的所有位向左或向右移动指定的位数。
  • &和|：按位与和按位或，它们逐位组合两个数字并返回结果。
  • ~：补码或求反一元运算符，它反转所有位。

在继续之前，请确保您完全熟悉所有C#位运算符。

以下是我们添加到Belonging的函数

public uint AddToGear(uint gear)
		{
			return gear | (uint)(1 << this.Number);
		}
		public uint RemoveFromGear(uint gear)
		{
			return gear & ~(uint)(1 << this.Number);
		}
		public bool IsInGear(uint gear)
		{
			return (gear & (1 << this.Number)) == (1 << this.Number);
		}
		public int GramsWeightInGear(uint gear)
		{
			return this.IsInGear(gear) ? this.GramsWeight : 0;
		}
		public int ValueInGear (uint gear)
		{
			return this.IsInGear(gear) ? this.Value : 0;
		}

成功！我们的测试全部通过，我们可以继续测试和开发Inventory。

库存的函数

我们首先测试非常简单的求和函数。我们的测试创建一个包含3个物品的allKit物品集。然后，我们添加allKit中的第一个和最后一个物品，并确保在对Inventory调用求和函数时得到正确的总和。

		[TestClass]
		public class TestInventory : TestKnapsack
		{
			[TestMethod]
			public void ShouldSumProperly()
			{
				var allKit = new List<Belonging>();
				allKit.Add(new Belonging { Number = 0, Name = "map", GramsWeight = 90, Value = 150 });
				allKit.Add(new Belonging { Number = 1, Name = "compass", GramsWeight = 130, Value = 35 });
				allKit.Add(new Belonging { Number = 2, Name = "water", GramsWeight = 1530, Value = 300 });

				Inventory.AllGear = allKit;
				var testInventory = new Inventory { Gear = 0 };
				testInventory.Gear = allKit[0].AddToGear(
					testInventory.Gear);
				testInventory.Gear = allKit[2].AddToGear(
					testInventory.Gear);

				Assert.AreEqual(allKit[0].GramsWeight + allKit[2].GramsWeight,
					testInventory.TotalGramsWeight);
				Assert.AreEqual(allKit[0].Value + allKit[2].Value,
					testInventory.TotalValue);
			}
		}

以下是将添加到Inventory的求和函数

		public int TotalGramsWeight { get { return Inventory.TotalGramsWeightForGear(this.Gear); } }
		public int TotalValue { get { return Inventory.TotalValueForGear(this.Gear); } }

		public static int TotalGramsWeightForGear (uint gear)
		{
				return AllGear.Select(o => 
					o.GramsWeightInGear(gear))
					.Sum();
			}

		public static int TotalValueForGear(uint gear)
		{
				return AllGear.Select(o => 
					o.ValueInGear(gear))
					.Sum();
			}

nothing too complicated, and the tests all still pass. Next we move on to the actual search for the valid inventories

库存的搜索函数

			[TestMethod]
			public void TestFirstBestInventory()
			{
				var allKit = new List<Belonging>();
				allKit.Add(new Belonging { Number = 0, Name = "map", GramsWeight = 90, Value = 150 });
				allKit.Add(new Belonging { Number = 1, Name = "compass", GramsWeight = 130, Value = 35 });
				allKit.Add(new Belonging { Number = 2, Name = "water", GramsWeight = 1530, Value = 300 });
				Inventory.AllGear = allKit;

				Assert.IsTrue(
					allKit[1].IsInGear(
					Inventory.FirstBestInventory(220).Gear));

				Assert.IsFalse(
					allKit[2].IsInGear(
					Inventory.FirstBestInventory(220).Gear));
			}

			[TestMethod]
			public void TestValidInventories()
			{
				var allKit = new List<Belonging>();
				allKit.Add(new Belonging { Number = 0, Name = "map", GramsWeight = 90, Value = 150 });
				allKit.Add(new Belonging { Number = 1, Name = "compass", GramsWeight = 130, Value = 35 });
				allKit.Add(new Belonging { Number = 2, Name = "water", GramsWeight = 1530, Value = 300 });
				Inventory.AllGear = allKit;

				// nothing except the empty inventory - so only one possible empty inventory
				Assert.AreEqual(1, Inventory.ValidInventories(5).Count());

				// since the upper weight limit is so large we end up with all possible inventories over 3 belongings, which is 8 including the empty inventory
				Assert.AreEqual(8, Inventory.ValidInventories(5000).Count());
			}

我们将新函数实现为Invetory如下

	public static uint NumberOfCombinations
		{
			get
			{
				return (~(uint)0 % (uint)(1 << AllGear.Count()));
			}
		}

		public static Inventory FirstBestInventory(int maxGramsWeight)
		{
			var numberOfCombinations = Inventory.NumberOfCombinations;
			int currentMaxValue = 0, overallBestValue = 0;
			var bestInventory = new Inventory();

			for (uint g = 0; g <= numberOfCombinations; g++)
				if (Inventory.TotalGramsWeightForGear(g) <= maxGramsWeight &&
					(currentMaxValue = Inventory.TotalValueForGear(g)) > overallBestValue)
				{
					bestInventory = new Inventory
					{
						Gear = g
					};
					overallBestValue = currentMaxValue;
				}

			return bestInventory;
		}

		public static IQueryable<Inventory> ValidInventories(int maxGramsWeight)
		{
			var numberOfCombinations = Inventory.NumberOfCombinations;
			var validInventories = new List<Inventory>();

			for (uint g = 0; g <= numberOfCombinations; g++)
				if (Inventory.TotalGramsWeightForGear(g) <= maxGramsWeight)
					validInventories.Add(new Inventory
					{
						Gear = g
					}
					);

			return validInventories.AsQueryable();
		}

最终总结

再次测试所有内容并使所有测试仍然通过后，我们就快完成了。我们最后的工作是创建漂亮的ToString()打印方法，并将所有内容放在main方法中，这将是控制台应用程序的入口点。

我们将以下内容添加到Belonging

		public override string ToString()
		{
			return string.Format("{0}, {1} g, valued at {2}",
				this.Name,
				this.GramsWeight,
				this.Value);
		}

我们也希望Inventory有漂亮的打印输出，所以我们将其添加进去

public override string ToString()
		{
			StringBuilder sb = new StringBuilder();
			sb.AppendLine("---- Inventory Start:");
			AllGear.Where(o => o.IsInGear(this.Gear))
				.ToList()
				.ForEach(o => sb.AppendLine(o.ToString()));
			sb.AppendFormat("---- Inventory End: Total Weight: {0} g, Total Value: {1}",
				this.TotalGramsWeight,
				this.TotalValue);
			return sb.ToString();
		}

最后，我们添加main方法，以及一个用于设置我们所有装备的小型辅助方法

class Program
	{
		static void Main(string[] args)
		{
			var allKit = LoadData();

			Inventory.AllGear = allKit;

			var bestInventories = Inventory
				.ValidInventories(maxGramsWeight: 4000)
				.OrderByDescending(o => o.TotalValue)
				.Take(5)
				.ToList();

			if (bestInventories.Count() == 0)
				Console.WriteLine("No inventory match the requirements.");
			else
			Console.WriteLine(string.Format("Best {0} inventories in descending order of value are:",bestInventories.Count()));
			bestInventories.ForEach(o =>
				Console.WriteLine(o)
				);

			var firstBestInventory = Inventory.FirstBestInventory( maxGramsWeight: 4000 );
			if (firstBestInventory == null)
				Console.WriteLine("No first best inventory found.");
			else
			{
				Console.WriteLine("Best inventory found: ");
				Console.WriteLine(firstBestInventory);
			}
		}

		private static List<Belonging> LoadData()
		{
			var allKit = new List<Belonging>();
			allKit.Add(new Belonging { Number = 0, Name = "map", GramsWeight = 90, Value = 150 });
			allKit.Add(new Belonging { Number = 1, Name = "compass", GramsWeight = 130, Value = 35 });
			allKit.Add(new Belonging { Number = 2, Name = "water", GramsWeight = 1530, Value = 300 });
			allKit.Add(new Belonging { Number = 3, Name = "Gold bar", GramsWeight = 3000, Value = 130 });
			allKit.Add(new Belonging { Number = 4, Name = "sandwich", GramsWeight = 500, Value = 160 });
			allKit.Add(new Belonging { Number = 5, Name = "glucose", GramsWeight = 150, Value = 60 });
			allKit.Add(new Belonging { Number = 6, Name = "tin", GramsWeight = 680, Value = 45 });
			allKit.Add(new Belonging { Number = 7, Name = "banana", GramsWeight = 270, Value = 60 });
			allKit.Add(new Belonging { Number = 8, Name = "apple", GramsWeight = 390, Value = 40 });
			allKit.Add(new Belonging { Number = 9, Name = "cheese", GramsWeight = 230, Value = 30 });
			allKit.Add(new Belonging { Number = 10, Name = "beer", GramsWeight = 620, Value = 10 });
			allKit.Add(new Belonging { Number = 11, Name = "suntan cream", GramsWeight = 110, Value = 70 });
			allKit.Add(new Belonging { Number = 12, Name = "camera", GramsWeight = 320, Value = 30 });
			allKit.Add(new Belonging { Number = 13, Name = "T-shirt", GramsWeight = 240, Value = 15 });
			allKit.Add(new Belonging { Number = 14, Name = "trousers", GramsWeight = 480, Value = 10 });

			return allKit;
		}
	}

完成了！让我们试试看……

我们完成了！让我们看看运行所有内容会得到什么

按价值降序排列的5个最佳库存是

---- Inventory Start:
map, 90 g, valued at 150
compass, 130 g, valued at 35
water, 1530 g, valued at 300
sandwich, 500 g, valued at 160
glucose, 150 g, valued at 60
banana, 270 g, valued at 60
apple, 390 g, valued at 40
cheese, 230 g, valued at 30
suntan cream, 110 g, valued at 70
camera, 320 g, valued at 30
T-shirt, 240 g, valued at 15
---- Inventory End: Total Weight: 3960 g, Total Value: 950
---- Inventory Start:
map, 90 g, valued at 150
compass, 130 g, valued at 35
water, 1530 g, valued at 300
sandwich, 500 g, valued at 160
glucose, 150 g, valued at 60
banana, 270 g, valued at 60
apple, 390 g, valued at 40
cheese, 230 g, valued at 30
suntan cream, 110 g, valued at 70
camera, 320 g, valued at 30
---- Inventory End: Total Weight: 3720 g, Total Value: 935
---- Inventory Start:
map, 90 g, valued at 150
compass, 130 g, valued at 35
water, 1530 g, valued at 300
sandwich, 500 g, valued at 160
glucose, 150 g, valued at 60
tin, 680 g, valued at 45
banana, 270 g, valued at 60
cheese, 230 g, valued at 30
suntan cream, 110 g, valued at 70
T-shirt, 240 g, valued at 15
---- Inventory End: Total Weight: 3930 g, Total Value: 925
---- Inventory Start:
map, 90 g, valued at 150
compass, 130 g, valued at 35
water, 1530 g, valued at 300
sandwich, 500 g, valued at 160
glucose, 150 g, valued at 60
tin, 680 g, valued at 45
banana, 270 g, valued at 60
apple, 390 g, valued at 40
suntan cream, 110 g, valued at 70
---- Inventory End: Total Weight: 3850 g, Total Value: 920
---- Inventory Start:
map, 90 g, valued at 150
compass, 130 g, valued at 35
water, 1530 g, valued at 300
sandwich, 500 g, valued at 160
glucose, 150 g, valued at 60
banana, 270 g, valued at 60
apple, 390 g, valued at 40
cheese, 230 g, valued at 30
suntan cream, 110 g, valued at 70
T-shirt, 240 g, valued at 15
---- Inventory End: Total Weight: 3640 g, Total Value: 920
Best inventory found: 
---- Inventory Start:
map, 90 g, valued at 150
compass, 130 g, valued at 35
water, 1530 g, valued at 300
sandwich, 500 g, valued at 160
glucose, 150 g, valued at 60
banana, 270 g, valued at 60
apple, 390 g, valued at 40
cheese, 230 g, valued at 30
suntan cream, 110 g, valued at 70
camera, 320 g, valued at 30
T-shirt, 240 g, valued at 15
---- Inventory End: Total Weight: 3960 g, Total Value: 950

结论

我们已经解决了背包问题的0/1版本，并且很有趣！我们的解决方案不仅经过了良好的测试，而且运行速度很快，对于物品数量较少的情况。

在本系列后续的文章中，我们将扩展我们的解决方案，测试更多物品数量的情况，并 hopefully 尝试解决这个有趣的计算机科学问题的其他更难的版本。

谁知道呢，也许我们甚至会尝试量子算法！

如果我们可以整天做这种编程就好了……

完整的解决方案在此GitHub上可用

© . All rights reserved.