algorithm - 我如何才能有效地找到保持在预算范围内并最大化效用的事件子集？

Question

我正在尝试开发一种算法，以从更大的列表中选择一部分事件。如果选择，每个事件都会使用一定数量的固定资源(即所选事件的总和必须保持在总预算之下)。可能存在多个可行子集，从中选择的方式将基于计算未选择事件的机会成本。

---

编辑: 这不是 0-1 knapsack problem 有两个原因:

• 背包的重量(即消耗的资源)需要整数值，而我的资源消耗(即背包用语中的质量)是一个连续变量。 (显然，可以选择一定程度的精度并量化所需的资源，但我的 bin 大小必须非常小，并且 Knapsack 在 W 中为 O(2^n)。
• 我无法先验地计算机会成本；也就是说，我无法独立评估每个人的适合度，尽管我可以评估一组给定的选定事件的效用或将额外任务添加到现有列表的边际效用。

---

我所做的研究提出了一种天真的方法:

Define the powerset
For each element of the powerset, calculate it's utility based on the items not in the set
Select the element with the highest utility

但是，我知道有一些方法可以加快执行时间和所需内存。例如:

• 完全枚举一个幂集是 O(2^n)，但我不需要完全枚举列表，因为一旦我找到一组超出预算的任务，我就知道任何增加更多任务的集合都是不可行的，可以被拒绝。也就是说，如果 {1,2,3,4} 是不可行的，那么 {1,2,3,4} U {n} 也是不可行的，其中 n 是任意一个较大列表中剩余的任务。
• 因为我只是总结职责，所以任务的顺序并不重要(即如果 {1,2,3} 可行，那么 {2,1,3} 、{3,2,1} 等)。
• 最后我需要的只是选定的集合，所以我可能只需要迄今为止找到的最佳效用值来进行比较。
• 我不需要保留列表枚举，只要我可以确定我已经查看了所有可行的列表即可。 (尽管我认为保留先前计算的可行子集的责任和可能会加快运行时间。)

我已经说服自己一个好的递归算法会起作用，但我无法弄清楚如何定义它，即使是在伪代码中(这可能最有意义，因为它将以多种语言实现--可能是用于原型(prototype)制作的 Matlab，然后是编译语言)。

Answer 1

knapsack problem是 NP 完全的，这意味着没有解决问题的有效方法。然而，有一个使用动态规划的伪多项式时间解决方案。查看Wikipedia section了解更多详情。

但是，如果最大效用很大，您应该坚持使用近似算法。一种这样的近似方案是贪婪地选择具有最大效用/成本的项目。如果预算很大而每个项目的成本很小，那么这会很有效。

编辑:由于您是根据不在集合中的项目定义效用，因此您可以简单地重新定义成本。抵消成本，然后转移一切，使您的所有值(value)都是积极的。