算法的内部预算最高值 [英] Algorithm for highest value inside budget

问题描述

我不能完全肯定要问这个问题（或做研究，看它是否已被previously回答）的最佳方式。

I wasn't entirely sure the best way to ask this question (or do the research to see if it has been previously answered).

由于其中每个条目都有一个点值和美元价值的数据集，我期待生成产生最高总分值的同时保持预算B内部长度为N项的列表。

Given a data set where each entry has a Point value and a Dollar value, I'm looking to generate a list of length N entries that yields the highest aggregate Point value whilst staying within budget B.

例如数据集：

Item    Points    Dollars
Apple   3.0       $1.00
Pear    2.5       $0.75
Peach   2.8       $0.88

和本（小）的数据集，说我的预算（B）为$ 2.25和列表长度（N）必须2.您必须使用固定列表的长度，但不可以要求使用预算的所有

And with this (small) data set, say my budget (B) is $2.25, and list length (N) must be 2. You MUST use the fixed list length, but are not required to use ALL of the budget.

显然所提供的例子是很容易做到在一个人的头上，而是赋予了更大的数据集，并双双走高N和B值，我在寻找一种算法，可以生成列表。有一个很难包装我的头，围绕这一个。

Obviously the example provided is easy to do in one's head, but given a much larger data set, and both higher N and B values, I'm looking for an algorithm that can generate the list. Having a hard time wrapping my head around this one.

只是寻找一个伪算法，但如果你preFER任何给定的语言感到自由与回应！

Just looking for a pseudo-algorithm, but if you prefer any given language feel free to respond with that!

推荐答案

我是相当积极的，这可以减少到一个NP完全问题，因此它不是真的值得尝试开发一个程序，将永远给你正确的答案，很多人都尝试过，并不能有效地做到这一点在一个大的数据集。但是，你可以用一个更有效的逼近技术，虽然它并不能保证给你正确的答案，许多流行的近似算法能够实现高精确度。

I am quite positive that this can be reduced to an NP-complete problem and hence it's not really worth trying to develop a process that will always give you the 'correct' answer as many people have tried and failed to do this efficiently over a large data set. However, you can use a much more efficient approximation technique that whilst it will not guarantee to give you the correct answer, many popular approximation algorithms are capable of achieving a high degree of accuracy.

希望这可以帮助你：）

这篇关于算法的内部预算最高值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！