algorithm - 多种背包变化

Question

我和本科生正在做一些关于多背包问题的进化算法工作。我已经完成了我的代码，但我很难理解测试用例的一个方面。我注意到他们有一个约束(权重或成本)矩阵，而不是列表。为什么？为什么一个物体的成本应该取决于它在哪个背包里？我当然可以添加算法来实现这一点，但我不了解它的应用程序。我发现的每个测试用例都是这种格式。对于具有一维约束的矩阵或数据的任何帮助，我们将不胜感激。

Answer 1

正如一篇关于旅行推销员的热门论文所说:

The popularity of the travelings salesman problem does not originate from millions of salesman that want to calculate the optimal route.

根据您对问题的描述，我认为您在谈论 Multiple-Choice Knapsack Problem (第 12 页)。 P 是价格矩阵，W 是权重矩阵。

背包问题当然也是如此。虽然故事是关于背包的，但背包可以是任何东西。

以调度问题为例。假设您有一家(虚构的)医院，有三名员工:两名医生和一名护士。现在，每天都会列出这些员工必须执行的任务(例如检查患者、填写表格……)。现在我们可以将每个员工表示为一个背包，因为他们当天的工作时间有限。

任务的权重描述了员工 i 需要处理任务 j 的时间量。此外，它还可以用于指定禁止执行某项任务。例如在比利时，持有 A 级证书的护士是不允许给病人注入(inject)的。您可以通过指定护士需要数年时间来处理此类任务来强制执行此操作，因此该任务的“重量”相对于那个袋子的容量来说太大了。

So: w_ij describes the time employee i spends to carry out task j and is set above the capacity if that task cannot be carried out by that employee.

此外，值(value)还包括执行任务的质量。如果其中一位医生专攻心脏病，显然他对心脏病患者的诊断会更好。或者，您可以使用处理该任务所需支付给员工的金额的倒数(如果员工按每项任务支付)，以最大限度地降低成本。

So p_ij specifies the quality with which employee i will carry out task j, or for instance the inverse of the cost of employee i carrying out task j.

背包的最佳配置因此将指定员工当天将处理哪些任务，这样员工就不会工作超过允许的时间(或执行他/她未获得许可的任务)，并进一步优化服务质量或最大限度地降低运营成本。

So if x_ij=1, that means in the optimal scenario, employee i will carry out task j that day.

因此，一个典型的应用程序是多个员工/机器/服务器处理具有不同成本和界限的任务/问题/请求。

---

@IVlad 针对相关问题提出了一些建设性意见:

• 在分配问题中，目标是在二分图中构造一组边，使得没有两条边共享一个节点并且总权重最大化。人们不能(显然)将 MCKP 映射到 AP，因为权重会丢弃员工执行过多任务的情况，仅仅因为它是最佳的。

• 多目标变体将价格矩阵 P 转换为张量(或更多张量)，这样您就可以考虑不同的评估标准(例如质量和价格)价格)，并为这两个目标寻找最佳解决方案。