找到總計達到給定限制的記錄組合

Question

給定一組只包含整數元素的記錄，找到總計達到給定限制的（一個或全部）記錄組合。例如，如果具有表示水果和它們的特徵（元素）滿足的限制將是記錄是維生素A，B和C

Apple - A=10, B=5, C=15 
Orange - A=1, B=20, C=14 
Banana - A=4, B=9, C=5 

而限制是

For A - 13 to 15 
For B - 10 to 15 
For C - 20 to 25 

在這種情況下，組合蘋果和香蕉。有一種算法比蠻力更好嗎？

Answer 1

這是一個整數線性程序（具有常數目標函數）。

解決像這樣的問題是NP，但有解決方案可以有效地解決實際問題（甚至相當大的問題）。

一個這樣的求解器是GLPK。

尋找有效解決ILPs的算法是一個活躍的研究領域。有關於Integer Programming的維基百科頁面的一些信息。