我正在尝试开发一种算法来从更大的列表中选择活动的子集。如果选中,每个活动都会使用一定数量的固定资源(即所选活动的总和必须保持在总预算之下)。可能有多个可行子集,从中选择的方法将基于计算未选择活动的机会成本。
编辑:这不是0-1 背包问题有两个原因:
- 背包需要整数值作为重量(即消耗的资源),而我的资源消耗(即背包用语中的质量)是一个连续变量。(显然,可以选择某种程度的精度并量化所需的资源,但我的 bin 大小必须非常小,并且 Knapsack
O(2^n)
在 W 中。 - 我无法先验地计算机会成本;也就是说,我不能独立评估每个人的适合度,尽管我可以评估给定一组选定活动的效用或向现有列表添加额外任务的边际效用。
我所做的研究表明了一种幼稚的方法:
定义幂集
对于幂集的每个元素,根据不在集合中的项目计算它的效用
选择效用最高的元素
但是,我知道有一些方法可以加快执行时间和所需的内存。例如:
- 完全枚举 powerset 是
O(2^n)
,但我不需要完全枚举列表,因为一旦我发现一组超出预算的任务,我知道任何添加更多任务的集合都是不可行的并且可以被拒绝。也就是说,如果{1,2,3,4}
是不可行的,那么是不可行的{1,2,3,4} U {n}
,其中 n 是剩余在较大列表中的任何一项任务。 - 由于我只是在总结职责,因此任务的顺序并不重要(即,如果
{1,2,3}
可行,那么{2,1,3}
,{3,2,1}
等)。 - 最后我需要的只是选定的集合,所以我可能只需要迄今为止找到的最佳效用值来进行比较。
- 我不需要保留列表枚举,只要我可以确定我已经查看了所有可行的枚举。(尽管我认为保留先前计算的可行子集的占空比可能会加快运行时间。)
我已经说服自己一个好的递归算法会起作用,但我不知道如何定义它,即使是在伪代码中(这可能是最有意义的,因为它将用几种语言实现——可能Matlab 用于原型设计,然后是编译语言)。