算法找到最佳组合

Question

假设我有100个产品的清单,每个产品都有价格.每个还具有能量(kJ)测量值.

是否有可能找到15种产品的最佳组合,其中10美元以下的能量总和(kJ)最大,使用编程？

我知道C#,但任何语言都没问题.干杯.

更新:为背包问题找到一些示例源代码.有没有人知道在哪里找到一些.谷歌搜索了几个小时,如果可能的话,需要在明天之前进行排序.助教.

Answer 1

http://en.wikipedia.org/wiki/Knapsack_problem

该背包问题或背包问题是中的问题的组合优化:给定一组项目,每一个权重和的值,确定每个项目的数目的集合中的包括,以使总重量小于或等于一个给定限制,总值尽可能大.它的名字源于一个受到固定尺寸背包约束的人所面临的问题,并且必须填写最有价值的物品......

Answer 2

这听起来更像是线性编程问题.

非正式地,线性规划确定了在给定数学模型中获得最佳结果(例如最大利润或最低成本)的方式,并给出了一些表示为线性方程的要求列表.

查看Simplex方法.

Answer 3

这在整数线性规划中，优化受线性约束的线性方程，其中所有变量和系数都是整数。

\n\n

您希望变量 includeItem1, ..., includeItemN 具有约束 0 \xe2\x89\xa4 includeItem i \xe2\x89\xa4 1 对于i的所有值，以及 includeItem1 + ... + includeItemN \xe2\x89\xa4 15，并 includeItem1*priceItem1 + ... \xe2\x89\xa4 10，最大化 includeItem1*kilojouleItem1 + ....

\n\n

将其放入您最喜欢的整数线性规划求解器中并获得解决方案:)

\n\n

另请参阅http://en.wikipedia.org/wiki/Linear_programming

\n\n

说你的特定问题是 NP 完全问题是没有意义的，但它是 NP 完全（某种）问题的一个实例，因此理论上可能没有快速的方法来完成它。根据您想要达到的最优程度以及 ILP 求解器的工作速度，这在实践中可能是可行的。

\n\n

我不认为你的问题是 ILP 的特例，因此它特别容易解决。将其视为类似背包的问题，​​您可以限制自己查看 1..100 的所有子集，其中最多（或恰好）有 15 个元素，这是 n 中的多项式——它是 n 选择-15，小于 (n^15)/(15!)，但当 n = 100 时，这并不是很有用。

\n\n

如果您需要求解器程序的建议，我已经尝试过 glpk 并发现它用起来很愉快。如果你想要一些花钱的东西，我的讲师总是以 CPLEX 为例。

\n