如何以最少的访问次数（最有效）从位置 FIFO 中选择项目
How to choose items from locations FIFO with minimum visits (most efficiently)
我的数据库中有一个项目列表，其中包含以下位置的库存：我正在使用 Entity Framework 和 C#。
public class Item {
public int ID { get; set; }
public string Code { get; set; }
public int Age { get; set; }
public string Name { get; set; }
public List<Inventory> Inventory { get; set; }
}
public class Inventory {
public int ID { get; set; }
public int Qty { get; set; }
public Location Location { get; set; }
public int LocationID { get; set; }
public Item Item { get; set; }
public int ItemID { get; set; }
}
public class Location {
public int ID { get; set; }
public string Name { get; set; }
}
例如，假设我需要：
- 50 瓶可乐
- 100 瓶百事可乐
我有（年龄、姓名 - 数量、地点）
- 2、可乐 - 25、Loc1
- 2，百事可乐 - 100，Loc1
- 2、可乐 - 25、Loc2
- 1，可乐 - 50，Loc3
我需要能够按照最有效的选择顺序对该列表进行排序，该过程有 2 条规则：
- 需要先挑选最旧的项目（最低年龄的数字最先）
- 需要访问的地点尽可能少
在某些情况下会发生冲突，有一种方法可以通过访问多个项目的单个位置来提高效率，但它会留下一个旧产品，这没关系，但它必须遵守一些某种阈值取决于我们保存了多少位置访问或其他东西。
不管怎样，我都不知道从哪里开始编码。
如何做到这一点？
如果我们忘记年龄信息和物品数量，这相当于Set Cover问题，这已经是NP-hard；添加这些额外的要求只会让事情变得更加困难。
暴力枚举
我可能只是尝试按照位置数量递增的顺序枚举所有可能的位置集：即所有单个位置，然后是所有位置对，等等。在将位置添加到集合中的每个点，我会如果其中没有我仍然需要的项目，请忽略它。
您所需要的只是一种增量生成所有子集的方法（即这样我们就不会浪费时间考虑包含我们早期决定不需要的位置的子集），跟踪项目的数量生成每个类型时仍然需要的每种类型*。这有一个简单的递归；在此处搜索 "generate all subsets" 或 Google 应该可以找到它。要以增加的大小顺序生成它们，您需要一个从 1 到 |locations| 的最外层循环，并且您的递归函数将采用一个额外的参数来记录要添加的剩余位置数，您最初将其设置为该循环计数器，并减少每次递归调用。
* 注意： 它实际上并不像上面建议的那么简单，因为如果我们向包含旧项目的当前部分解决方案添加一个新位置，我们希望成为能够使用这些项目而不是我们之前挑选的项目。因此，我们需要跟踪的不仅仅是我们仍然需要选择的每种类型的项目数量：我们还需要跟踪，对于每种项目类型，每个年龄 [=] 的该类型 的项目数量39=] 我们已经选择了。我认为最简单的方法是在我们完成部分解决方案的构建之前根本不承诺选择项目；相反，我们跟踪我们访问的所有位置的项目和年龄的 "pool"，并且只在最后选择它们。具体来说，当我们构造一个部分解决方案时，对于每个所需的项目类型，我们保留一个按年龄递减顺序排序的列表（或者更好的是 heap/priority 队列——这将更快更新）包含一个（年龄，可用count) 对我们访问过的每个位置以及该商品的库存。然后当我们完成构建部分解决方案时，我们可以从这个列表的前面读取对（或弹出堆），直到我们提取了足够的项目；这些将是我们可以从我们访问的一组位置中获得的最古老的项目。
如何比较解决方案
在我们找到 "best" 解决方案之前，我们需要定义 "best" 的含义，这意味着我们需要一种方法来比较两个解决方案，看看哪个更好——换句话说，我们想要对有效解集的 order。对于这个问题，我们只有模糊的、相互竞争的要求，我们应该更喜欢访问较少位置的解决方案，以及使用旧项目的解决方案。这不足以完全指定订单，因此折衷方案是寻找一小组解决方案。我认为报告每个大小（位置数）的 "best" 解决方案会很有用——如果最多有 30 个库存记录，那么最多会有 30 个这样的解决方案，这应该是一个足够小的列表供人类一起工作。
即使我们只考虑特定大小的解决方案，我们在问题说明中仍然没有足够的信息来 select 特定订单 -- 是一个使用 25 天的 2 地点解决方案-与使用 50 天可乐物品和 25 天百事可乐物品的 2 地点解决方案相比，旧可乐物品和 50 天前百事可乐物品更好还是更差？尽管如此，我们仍然可以在 "obvious" 时寻找做出正确选择的订单，例如当一个解决方案中最旧的项目比另一个解决方案中的最新项目新时。以下两个订单都有这个 属性.
按最新项目排序：您可以跟踪到目前为止从当前部分解决方案（位置集）中的位置获取的最新项目。越旧的最新的项目，它的解决方案越好。
按平均项目年龄排序：有许多对相同大小的解决方案，之前的排序不会区分这些解决方案——具体来说，只要两个解决方案中的最新项目是相同的（或者只是年龄相同），它不会区分他们。因此，最好改为计算年龄的加权和——根据该年龄的项目数对每个年龄加权。这相当于最小化平均项目年龄（因为您可以通过除以项目总数得到它，这是固定的）。
最新项目排序方案在一个方面优于平均年龄方案：它允许（可能相当多）修剪较大的解决方案。例如，假设您有一个使用 3 个位置的解决方案，并且有一个 10 天前的最新项目。一旦您开始生成具有 4 个或更多位置的解决方案，您可以立即忽略任何 需要的项目 已存在 10 天或更短时间的任何位置 - 因为您已经有一个使用更少的解决方案位置并且具有相同或更好的最新年龄:)
我的数据库中有一个项目列表，其中包含以下位置的库存：我正在使用 Entity Framework 和 C#。
public class Item {
public int ID { get; set; }
public string Code { get; set; }
public int Age { get; set; }
public string Name { get; set; }
public List<Inventory> Inventory { get; set; }
}
public class Inventory {
public int ID { get; set; }
public int Qty { get; set; }
public Location Location { get; set; }
public int LocationID { get; set; }
public Item Item { get; set; }
public int ItemID { get; set; }
}
public class Location {
public int ID { get; set; }
public string Name { get; set; }
}
例如，假设我需要：
- 50 瓶可乐
- 100 瓶百事可乐
我有（年龄、姓名 - 数量、地点）
- 2、可乐 - 25、Loc1
- 2，百事可乐 - 100，Loc1
- 2、可乐 - 25、Loc2
- 1，可乐 - 50，Loc3
我需要能够按照最有效的选择顺序对该列表进行排序，该过程有 2 条规则：
- 需要先挑选最旧的项目（最低年龄的数字最先）
- 需要访问的地点尽可能少
在某些情况下会发生冲突，有一种方法可以通过访问多个项目的单个位置来提高效率，但它会留下一个旧产品，这没关系，但它必须遵守一些某种阈值取决于我们保存了多少位置访问或其他东西。
不管怎样，我都不知道从哪里开始编码。
如何做到这一点？
如果我们忘记年龄信息和物品数量，这相当于Set Cover问题，这已经是NP-hard；添加这些额外的要求只会让事情变得更加困难。
暴力枚举
我可能只是尝试按照位置数量递增的顺序枚举所有可能的位置集：即所有单个位置，然后是所有位置对，等等。在将位置添加到集合中的每个点，我会如果其中没有我仍然需要的项目，请忽略它。
您所需要的只是一种增量生成所有子集的方法（即这样我们就不会浪费时间考虑包含我们早期决定不需要的位置的子集），跟踪项目的数量生成每个类型时仍然需要的每种类型*。这有一个简单的递归；在此处搜索 "generate all subsets" 或 Google 应该可以找到它。要以增加的大小顺序生成它们，您需要一个从 1 到 |locations| 的最外层循环，并且您的递归函数将采用一个额外的参数来记录要添加的剩余位置数，您最初将其设置为该循环计数器，并减少每次递归调用。
* 注意： 它实际上并不像上面建议的那么简单，因为如果我们向包含旧项目的当前部分解决方案添加一个新位置，我们希望成为能够使用这些项目而不是我们之前挑选的项目。因此，我们需要跟踪的不仅仅是我们仍然需要选择的每种类型的项目数量：我们还需要跟踪，对于每种项目类型，每个年龄 [=] 的该类型 的项目数量39=] 我们已经选择了。我认为最简单的方法是在我们完成部分解决方案的构建之前根本不承诺选择项目；相反，我们跟踪我们访问的所有位置的项目和年龄的 "pool"，并且只在最后选择它们。具体来说，当我们构造一个部分解决方案时，对于每个所需的项目类型，我们保留一个按年龄递减顺序排序的列表（或者更好的是 heap/priority 队列——这将更快更新）包含一个（年龄，可用count) 对我们访问过的每个位置以及该商品的库存。然后当我们完成构建部分解决方案时，我们可以从这个列表的前面读取对（或弹出堆），直到我们提取了足够的项目；这些将是我们可以从我们访问的一组位置中获得的最古老的项目。
如何比较解决方案
在我们找到 "best" 解决方案之前，我们需要定义 "best" 的含义，这意味着我们需要一种方法来比较两个解决方案，看看哪个更好——换句话说，我们想要对有效解集的 order。对于这个问题，我们只有模糊的、相互竞争的要求，我们应该更喜欢访问较少位置的解决方案，以及使用旧项目的解决方案。这不足以完全指定订单，因此折衷方案是寻找一小组解决方案。我认为报告每个大小（位置数）的 "best" 解决方案会很有用——如果最多有 30 个库存记录，那么最多会有 30 个这样的解决方案，这应该是一个足够小的列表供人类一起工作。
即使我们只考虑特定大小的解决方案，我们在问题说明中仍然没有足够的信息来 select 特定订单 -- 是一个使用 25 天的 2 地点解决方案-与使用 50 天可乐物品和 25 天百事可乐物品的 2 地点解决方案相比，旧可乐物品和 50 天前百事可乐物品更好还是更差？尽管如此，我们仍然可以在 "obvious" 时寻找做出正确选择的订单，例如当一个解决方案中最旧的项目比另一个解决方案中的最新项目新时。以下两个订单都有这个 属性.
按最新项目排序：您可以跟踪到目前为止从当前部分解决方案（位置集）中的位置获取的最新项目。越旧的最新的项目，它的解决方案越好。
按平均项目年龄排序：有许多对相同大小的解决方案，之前的排序不会区分这些解决方案——具体来说，只要两个解决方案中的最新项目是相同的（或者只是年龄相同），它不会区分他们。因此，最好改为计算年龄的加权和——根据该年龄的项目数对每个年龄加权。这相当于最小化平均项目年龄（因为您可以通过除以项目总数得到它，这是固定的）。
最新项目排序方案在一个方面优于平均年龄方案：它允许（可能相当多）修剪较大的解决方案。例如，假设您有一个使用 3 个位置的解决方案，并且有一个 10 天前的最新项目。一旦您开始生成具有 4 个或更多位置的解决方案，您可以立即忽略任何 需要的项目 已存在 10 天或更短时间的任何位置 - 因为您已经有一个使用更少的解决方案位置并且具有相同或更好的最新年龄:)