我试图开发一个算法，从一个更大的列表中选择一个子集的活动。如果选中，则每个活动都会使用一定数量的固定资源（即所选活动的总和必须保持在总预算之下）。可能存在多个可行子集，从这些子集中选择的方法将基于计算未选择活动的机会成本。
编辑：这不是0-1 knapsack problem有两个原因：
背包的重量（即消耗的资源）需要整数值，而我的资源消耗（即背包中的质量）是一个连续变量（很明显，可以选择一些精度级别并量化所需的资源，但是我的箱子必须非常小，背包在w中O(2^n)。
我不能先验地计算机会成本，也就是说，我不能独立评估每一个机会的成本，虽然我可以评估一组给定活动的效用或从增加一个额外的任务到现有列表的边际效用。
我所做的研究表明了一种幼稚的方法：
定义powerset
对于powerset的每个元素，根据集合中不包含的项计算其效用
选择效用最高的元素
但是，我知道有一些方法可以加快执行时间和所需内存。例如：
完全枚举一个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进行原型设计，然后用编译语言）。
最佳答案
knapsack problem是np完全的，这意味着没有有效的解决问题的方法。然而，使用动态规划有一个伪多项式时间解。有关详细信息，请参见上面的Wikipedia section。
然而，如果效用最大，则应该坚持近似算法。一个这样的近似方案是贪婪地选择具有最大效用/成本的项目。如果预算大，每个项目的成本小，那么这可以很好地解决。
编辑：由于您是根据不在集合中的项目定义实用程序，所以您可以简单地重新定义成本否定成本，然后改变一切，使你的所有价值观都是积极的。