Аналогично задаче размена монеты, но с повторениями «монет» и другой целью оптимизации. ⇐ Python

[Anonymous]

Цель — получить список всех возможных вариантов последовательностей целых положительных значений (номинальная монета) из списка L, где каждое целое число (номинальная монета)< Значение /em> можно использовать несколько раз (т. е. допускать повторения), где сумма значений (номинальная монета) равна targetSum с ограничением, что общее количество чисел *(монеты) в сгенерированном варианте последовательность ограничена диапазоном между n и m (включая n и m).
Код ниже — это то, что я придумал на данный момент, но он работает слишком медленно, чтобы быть частью задачи оптимизации:

Код: Выделить всё

def allArrangementsOfIntegerItemsInLsummingUpTOtargetSum(L, targetSum, n=None, m=None):
if n is None:   n  = 1
if m is None:   m = targetSum
lenL = len(L)
# print(f"{targetSum=}, {L=}, {n=}, {m=}")
Stack           = []
# Initialize the Stack with the starting point for each element in L
for i in range(lenL):
currentSum  =   L[ i ]
path        = [   L[ i ]   ]
start       = 0         # Start from 0 allows revisiting of all items
Stack.append(   (currentSum, path, start )   )

while Stack:
currentSum, path, start = Stack.pop()
# Check if the current path meets the criteria
if currentSum == targetSum and n  m:
continue
# ^ - NEXT please: stop exploring this path as it's not valid or complete

# Continue to build the path by adding elements from L, starting from 0 index
for i in range(len(L)):  # Change start to 0 if you want to include all permutations
newSum = currentSum + L[ i  ]
newPath = path + [ L[ i  ]  ]
Stack.append((newSum, newPath, 0))  # Start from 0 allows every possibility
# def allArrangementsOfIntegerItemsInLsummingUpTOtargetSum
splitsGenerator = allArrangementsOfIntegerItemsInLsummingUpTOtargetSum

L = [ 13, 17, 23, 24, 25 ] ; targetSum = 30 ; m=1 ; n=30
sT=T(); listOfSplits = list(splitsGenerator(L, targetSum) ); eT=T(); dT=eT-sT
print( f"{dT=:.6f} s  ->  L = [ 13, 17, 23, 24, 25 ] ; targetSum =   30  ->  {listOfSplits}")

L = [ 60, 61, 62, 63, 64 ] ; targetSum = 600 # m=1 ; n=6000 are DEFAULT values
sT=T(); listOfSplits = list(splitsGenerator(L, targetSum) ); eT=T(); dT=eT-sT
print( f"{dT=:.6f} s  ->  L = [ 60, 61, 62, 63, 64 ] ; targetSum = 6000  ->  {listOfSplits}")

предоставление в качестве вывода:

Код: Выделить всё

dT=0.000047 s  ->  L = [ 13, 17, 23, 24, 25 ] ; targetSum =  30  ->  [[17, 13], [13, 17]]
dT=5.487905 s  ->  L = [ 60, 61, 62, 63, 64 ] ; targetSum = 600  ->  [[60, 60, 60, 60, 60, 60, 60, 60, 60, 60]]

где вы можете видеть, что алгоритму требуется более 5 секунд, чтобы найти единственно возможный вариант, выполняя такие же вычисления для targetSum = 6000, продолжающиеся «вечно».
p>
Есть идеи, как написать код, способный дать результат хотя бы на порядок быстрее?
Я уже несколько недель искал в Интернете и обнаружил, что все известные подходы оптимизации, основанные на ранце, размене монет и динамическом программировании, не охватывают такую ​​​​основную задачу, какой специальный случай следует использовать для разделения списка элементов на подсписки (разделы) с размерами от до b с целью оптимизации общей весовой функции, которая использует значения, полученные из локальной весовой функции, вычисляющей отдельные веса элементов в каждом подсписке (разделе).
Обратите внимание, что обе последовательности [[17, 13], [13, 17]] состоят из одинаковых значений (номинальная монета). Другими словами, порядок значений имеет значение, давая два варианта вместо одного, если порядок был выбран намеренно.
Меня интересует другой алгоритм, способный дать результат гораздо быстрее. , поэтому язык программирования, на котором этот алгоритм написан или выражен, является второстепенным, но я бы предпочел, чтобы Python описывал алгоритм, поскольку это позволит в качестве побочного эффекта легко протестировать его на основе уже предоставленного кода.
ОБНОВЛЕНИЕ с учетом кода, предоставленного в ответе MS:

Код: Выделить всё

def count_combinations(L, targetSum, n=None, m=None):
if n is None:   n  = 1
if m is None:   m = targetSum
# Create the DP table with dimensions (m+1) x (targetSum+1)
dp = [[0] * (targetSum + 1) for _ in range(m + 1)]
dp[0][0] = 1  # Base case

# Update the DP table
for num in L:
for count in range(m, n - 1, -1):  # Go from m to n
for sum_val in range(num, targetSum + 1):
dp[count][sum_val] += dp[count - 1][sum_val - num]

# Extract all valid combinations
result = []
for count in range(n, m + 1):
if dp[count][targetSum] > 0:
result.extend(extract_combinations(L, count, targetSum, dp))

return result

def extract_combinations(L, count, targetSum, dp):
combinations = []

def backtrack(current_count, current_sum, combination):
if current_count == 0 and current_sum == 0:
combinations.append(combination.copy())
return
if current_count  0:
combination.append(num)
backtrack(current_count-1, current_sum-num, combination)
combination.pop()

backtrack(count, targetSum, [])
return combinations

splitsGenerator = count_combinations

L = [ 13, 17, 23, 24, 25 ] ; targetSum = 30 ; m=1 ; n=30
sT=T(); listOfSplits = list(splitsGenerator(L, targetSum) ); eT=T(); dT=eT-sT
print( f"{dT=:.6f} s  ->  L = [ 13, 17, 23, 24, 25 ] ; targetSum =   30  ->  {listOfSplits}")

L = [ 60, 61, 62, 63, 64 ] ; targetSum = 600 # m=1 ; n=6000 are DEFAULT values
sT=T(); listOfSplits = list(splitsGenerator(L, targetSum) ); eT=T(); dT=eT-sT
print( f"{dT=:.6f} s  ->  L = [ 60, 61, 62, 63, 64 ] ; targetSum = 6000  ->  {listOfSplits}")

что выводит:

Код: Выделить всё

dT=0.000469 s  ->  L = [ 13, 17, 23, 24, 25 ] ; targetSum =   30  ->  [[13, 17], [17, 13]]
dT=0.285951 s  ->  L = [ 60, 61, 62, 63, 64 ] ; targetSum = 6000  ->  []

не удалось предоставить результат во втором примере.

ОБНОВЛЕНИЕ с учетом краткости превосходный код, предоставленный в ответе chrslg:

Код: Выделить всё

def bb3( L, target, partial=[]):
if target < 0  : return []
if target ==0 : return [partial]
if target=c:
sols.extend( bb3(L, target-c, partial+[c]) )
return sols

splitsGenerator = bb3

L = [ 13, 17, 23, 24, 25 ] ; targetSum = 30 ; m=1 ; n=30 # m=1 ; n=30 are DEFAULT values
sT=T(); listOfSplits = list(splitsGenerator(L, targetSum) ); eT=T(); dT=eT-sT
print( f"{dT=:.6f} s  ->  L = [ 13, 17, 23, 24, 25 ] ; targetSum =   30  ->  {listOfSplits}")

L = [ 60, 61, 62, 63, 64 ] ; targetSum = 600 # m=1 ; n=6000 are DEFAULT values
sT=T(); listOfSplits = list(splitsGenerator(L, targetSum) ); eT=T(); dT=eT-sT
print( f"{dT=:.6f} s  ->  L = [ 60, 61, 62, 63, 64 ] ; targetSum = 6000  ->  {listOfSplits}")

выходы:

Код: Выделить всё

dT=0.000012 s  ->  L = [ 13, 17, 23, 24, 25 ] ; targetSum =   30  ->  [[13, 17], [17, 13]]
dT=0.933661 s  ->  L = [ 60, 61, 62, 63, 64 ] ; targetSum = 6000  ->  [[60, 60, 60, 60, 60, 60, 60, 60, 60, 60]]

работает в 4–6 раз быстрее, чем код, который я предоставил для справки.
Учитывая, что для получения очевидного результата требуется почти одна секунда во втором случае это все еще превосходит ожидания, по крайней мере, на порядок.
Я начал с рекурсивного подхода, но поскольку рекурсия может наталкиваться на рекурсию, ограничивает код, который я предоставил в вопросе это переписанная версия рекурсивной версии, и поэтому может быть она стала медленнее из-за замены рекурсии на Stack ?


Подробнее здесь: https://stackoverflow.com/questions/783 ... her-optimi