У меня есть несколько векторов оценок, например:
A = [1,2,3,4]
B = [6,8,2,1]
C = [2,7,9,4]
D = [4,3,2,1]
Где каждая позиция оценки соответствует стоимости в отдельном векторе затрат:
cost = [0.25,0.5,0.75,1]
Например, выбирая '8 'из вектора B стоит 0,5.
. Как выбрать только один элемент от каждого из A до D, который максимизирует значение суммы (в соответствии с проблемой ранца). Это подчиняется двум ограничениям:
1) бюджетное ограничение. т. е. если '*' обозначает положение оптимальной комбинации в векторе, то:
cost[A*]+cost[B*]+cost[C*]+cost[D*] == budget
2) ограничение диапазона для каждого вектора, так что есть минимальные и максимальные затраты от каждого вектора, которые могут быть установленным то есть:
0.2 < cost[C*] < 0.6
Я пытался использовать грубую версию http://rosettacode.org/wiki/Knapsack_problem/0-1#C .2B.2B . Но я не был уверен, как расширить его на несколько списков, и я уверен, что есть более элегантное решение. Не обязательно должен быть подход ранца.