Если нет никаких ограничений на значения внутри ваших триплетов, то мы сталкиваемся с довольно общей версией задачи целочисленного программирования , более конкретно, с проблемой линейного программирования 0-1, так как ее можно представить в видесистема уравнений с каждым коэффициентом, равным 0 или 1. Вы можете найти возможные подходы на вики-странице, но нет простого и быстрого решения этой проблемы в целом.
В качестве альтернативы, если второечисла каждой пары (те, которые должны суммироваться до >= P) взяты из достаточно небольшого диапазона, мы могли бы рассматривать это как проблему динамического программирования, аналогичную проблеме Knapsack .«Достаточно маленький» определить довольно сложно, поскольку исходные данные имеют нецелые числа.Если они были целыми числами, то алгоритмическая сложность решения, которое я опишу, равна O(P * N).Для нецелых чисел их необходимо сначала преобразовать в целые числа, умножив их все, а также P на достаточно большое число.В вашем примере точность каждого числа равна 1 цифре после нуля, поэтому достаточно умножения на 10.Следовательно, фактическая сложность равна O(M * P * N), где M - это коэффициент, на который умножилось все для достижения целых чисел.
После этого мы, по сути, решаем модифицированную задачу о ранце: вместо ограничения веса сверху,мы ограничиваем его снизу, и на каждом шаге мы выбираем пару из триплета, а не решаем, помещать ли предмет в рюкзак или нет.
Давайте определим функцию minimum_sum[i][s], которая взначения i, s представляют минимально возможную сумму (первых чисел в каждой взятой нами паре), которую мы можем достичь, если сумма вторых чисел в парах, взятых до сих пор, равна s, и мы уже рассмотрели первые i триплеты,Единственным исключением из этого определения является то, что minimum_sum[i][P] имеет минимум для всех сумм, превышающих также P.Если мы сможем вычислить все значения этой функции, тогда ответом будет minimum_sum[N][P].Значения функции могут быть вычислены с помощью чего-то вроде этого:
minimum_sum[0][0]=0, all other values are set to infinity
for i=0..N-1:
for s=0..P:
for j=0..2:
minimum_sum[i+1][min(P, s+B[i][j])] = min(minimum_sum[i+1][min(P, s+B[i][j])], minimum_sum[i][s] + A[i][j]
A[i][j] здесь обозначает первое число в j-й паре i-го триплета, а B[i][j] обозначает второе число в том же триплете.
Это решение является жизнеспособным, если N велико, но P мало и точность на B s не слишком высока.Например, если N=50, надежды на вычисление 3^N возможностей практически нет, но с M*P=1000000 этот подход будет работать очень быстро.
Реализация Python указанной выше идеи:
def compute(A, B, P):
n = len(A)
# note that I use 1,000,000 as “infinity” here, which might need to be increased depending on input data
best = [[1000000 for i in range(P + 1)] for j in range(n + 1)]
best[0][0] = 0
for i in range(n):
for s in range(P+1):
for j in range(3):
best[i+1][min(P, s+B[i][j])] = min(best[i+1][min(P, s+B[i][j])], best[i][s]+A[i][j])
return best[n][P]
Тестирование:
A=[[4, 5, 7], [7, 8, 1], [6, 1, 9]]
# second numbers in each pair after scaling them up to be integers
B=[[1, 3, 6], [2, 4, 4], [3, 2, 5]]
In [7]: compute(A, B, 0)
Out[7]: 6
In [14]: compute(A, B, 7)
Out[14]: 6
In [15]: compute(A, B, 8)
Out[15]: 7
In [20]: compute(A, B, 13)
Out[20]: 14