预算内最高值算法

Algorithm for highest value inside budget

我不完全确定提出这个问题的最佳方式(或者做研究看看以前是否有人回答过)。

给定一个数据集,其中每个条目都有一个点值和一个美元值,我希望生成一个长度为 N 的条目的列表,该列表产生最高的总点值,同时保持在预算 B 内。

示例数据集:

Item    Points    Dollars
Apple   3.0       .00
Pear    2.5       [=10=].75
Peach   2.8       [=10=].88

对于这个(小)数据集,假设我的预算 (B) 是 2.25 美元,列表长度 (N) 必须是 2。您必须使用固定的列表长度,但 不是 需要使用所有预算。

显然,所提供的示例很容易在头脑中完成,但如果数据集更大,并且 N 和 B 值都更高,我正在寻找可以生成列表的算法。很难理解这个问题。

只是在寻找一个伪算法,但如果您喜欢任何给定的语言,请随时回复!

我非常肯定这可以简化为一个 NP 完全问题,因此不值得尝试开发一个总是会给你 'correct' 答案的过程,因为许多人已经尝试过但都失败了在大型数据集上有效地执行此操作。然而,您可以使用更有效的近似技术,虽然它不能保证给您正确的答案,但许多流行的近似算法能够实现高精度。

希望这对您有所帮助:)

这个问题是 NP-Complete(NP 和 NP-Hard),意思是,直到现在还没有找到算法,可以在多项式时间(输入大小的多项式)内解决这个问题,如果你找到一个算法,你会解决计算机科学中最伟大的问题之一 (P=NP),你至少会带来一百万美元的奖励。

如果您对近似值感到满意,我会推荐贪心算法:

https://en.wikipedia.org/wiki/Greedy_algorithm