А зачем вам использовать ДП для данной задачи, когда переменные не целые? Используйте симплекс метод, это и проще и быстрее. Конечно, у него есть проблема с точностью при float, но если использовать натуральные дроби в расчётах, то всё решаемо.
Ну как же в вашем примере это и есть рюкзак, только с единичной стоимостью за каждый товар :), те каждый товар имеет одинаковый вес (стоимость).
Если 100 это не единицы, а например общий вес в килограммах, тогда ещё проще. Просто поменяем тип переменных на нецелочисленный.
Покажите, как набрать нецелочисленную сумму порядка 10^7 с помощью нескольких сотен нецелочисленных слагаемых
Это совсем просто, выполняет за секунду. Можно даже сделать минимальный порог, меньше которого нельзя набрать товара одного вида, например 1000 кг.
Код
import pulp as pl
import random as rnd
summa = 100000000
print('Сумма к которой стремимся:', summa)
n = 200 # Количество наименований
# Кортеж из максимального числа товара для заказа и цены
goods = [rnd.uniform(100000, 1000000) for i in range(n)]
print('Товарная номенклатура:', goods)
print()
# Объявляем модель
model = pl.LpProblem(name="test", sense=pl.LpMaximize)
# Подключаем решатель CBC
solver = pl.PULP_CBC_CMD(msg=True)
# Объявляем переменны
x = [pl.LpVariable(name=f'x{i:03}', cat='Continuous', lowBound=1000, upBound=goods[i]) for i in range(len(goods))]
# Целевая функция
model += pl.lpSum([x[i] for i in range(n)])
# Ограничение
model += pl.lpSum([x[i] for i in range(n)]) <= summa
# Выводим модель
# print(model)
# Находим решение
status = model.solve(solver)
if status == 1:
print('Фактически набрали:', sum(val.value() for val in model.variables()))
print('Заказать:')
for i, val in enumerate(model.variables()):
print(f'Товар{i} {val.value()} из {goods[i]}')
Сумма к которой стремимся: 100000000
Товарная номенклатура: [645691.2931885093, 317858.3130222785, 744057.5532077567, 133639.75382448838, 562529.939680595, 220121.72357789087, 868511.0402679854, 667797.8031388721, 388828.67949273606, 465363.4296413606, 403835.1071355331, 491265.3752803172, 862382.3549521483, 626751.8561946657, 752075.9914224785, 250814.25645500244, 694641.3500011705, 785298.1534501243, 756109.8824451261, 709645.6754570607, 917972.7722415725, 955554.7921899806, 844965.3743659591, 343735.3504507794, 460236.4328581181, 233724.30587792073, 893685.5343474532, 787940.3364260227, 719747.4481560593, 839276.7076206218, 171350.49046382695, 774521.6771186346, 769371.4382454185, 243399.19725691518, 818371.7224263975, 263151.0702352981, 676299.8690587819, 687833.2955874939, 112600.19384111586, 499453.031874757, 661994.231672027, 225596.36411810524, 958092.6936240986, 681207.4839389888, 221200.14850950055, 200157.84548828035, 286583.0234027279, 577355.6256299126, 333399.2612021096, 345060.8183317391, 240376.03111233027, 680518.4663040837, 463773.4974714662, 603426.9349440299, 585451.9677209563, 818634.3504291275, 171432.37501094883, 495861.8017951375, 103335.55560669722, 545972.0778357927, 937260.2539286873, 799451.2343092249, 417260.2715133255, 120591.66216110905, 358925.2599059303, 855285.4256332519, 347277.713113735, 372653.72638729645, 613341.4875585965, 834008.5598722058, 113592.21629697594, 194557.76160520766, 800146.2055155531, 156028.23439463944, 234383.65903390953, 621669.0491833334, 130080.20308397856, 544095.0768277377, 965060.2690712278, 199402.61458110923, 461476.2426870921, 271535.88928093534, 748673.3531951199, 291829.2366716161, 975848.7145694873, 485652.46757367696, 737538.760422223, 189907.22583928623, 109988.40031527661, 984319.965890239, 618869.2020713241, 362838.3468138749, 376860.5702819198, 322127.9759303717, 979302.096856456, 820451.3462925756, 189339.12006266386, 193907.17287269933, 748611.581533799, 655311.699386001, 796814.15879224, 423842.34665262274, 952255.412758336, 581889.2083885402, 722644.4024255745, 451917.5543063265, 785003.6822073464, 357255.87479735096, 951802.8429228318, 374079.6320391303, 424580.48065054807, 281567.7474588673, 298954.75890279224, 432199.85272635537, 581294.8771369768, 173356.4211978094, 706161.0307623808, 605862.960038322, 541192.3019834808, 329730.3633221672, 687708.8338998506, 330420.67869774863, 879502.9486966063, 808008.6649083216, 301853.2235122584, 203009.2664988107, 364144.00981451105, 627419.9685893131, 176633.14050900837, 340103.1123771363, 802280.9580293891, 444502.25690602284, 863546.4821482579, 248756.34119952025, 825107.119392471, 395423.0745651665, 708798.0964840548, 831190.0211546295, 661983.2835724461, 290013.1429606739, 262265.4727330602, 892882.5141660307, 155820.2331731233, 701627.5126059169, 805011.8389548, 687742.7342606192, 951532.8624331568, 573488.7620339128, 703435.5461830014, 825949.8310937249, 474429.0545429463, 622619.9695408016, 687086.0058438272, 934332.8887548604, 256323.9250997613, 593558.238855277, 949542.4556368465, 771376.9966740404, 786506.1936954544, 628402.9217995974, 231923.77522107676, 831762.7684432977, 414479.4428540272, 523589.8938237171, 258845.04426821976, 100903.96307715664, 163034.36959932314, 653401.590558145, 721290.1491665429, 186619.42698570632, 147015.38818919464, 141790.47086389558, 636990.7669476826, 736812.1654561599, 664545.766602985, 102627.77708906103, 786403.1857887985, 358518.36412963097, 635916.4400603629, 485805.0121598375, 468858.9812794371, 556002.1127324968, 973357.8578341331, 974833.2465184958, 242180.86936195672, 322935.57640718075, 748520.5761595789, 496686.76150578726, 325659.26421606675, 996816.1515029438, 765943.5165366514, 464941.89187614346, 784662.0608521587, 599685.5985937037, 555830.582672107, 273451.6046468464, 827005.4104140169, 772435.8386630347, 301427.2057494812, 211326.18839592487]
Фактически набрали: 99999999.99000001
Заказать:
Товар0 1000.0 из 645691.2931885093
Товар1 1000.0 из 317858.3130222785
Товар2 1000.0 из 744057.5532077567
Товар3 1000.0 из 133639.75382448838
Товар4 1000.0 из 562529.939680595
Товар5 1000.0 из 220121.72357789087
Товар6 1000.0 из 868511.0402679854
Товар7 1000.0 из 667797.8031388721
Товар8 1000.0 из 388828.67949273606
Товар9 1000.0 из 465363.4296413606
Товар10 1000.0 из 403835.1071355331
Товар11 1000.0 из 491265.3752803172
Товар12 1000.0 из 862382.3549521483
Товар13 1000.0 из 626751.8561946657
Товар14 165825.29 из 752075.9914224785
Товар15 250814.26 из 250814.25645500244
Товар16 694641.35 из 694641.3500011705
Товар17 785298.15 из 785298.1534501243
Товар18 756109.88 из 756109.8824451261
Товар19 709645.68 из 709645.6754570607
Товар20 917972.77 из 917972.7722415725
Товар21 955554.79 из 955554.7921899806
Товар22 844965.37 из 844965.3743659591
Товар23 343735.35 из 343735.3504507794
Товар24 460236.43 из 460236.4328581181
Товар25 233724.31 из 233724.30587792073
Товар26 893685.53 из 893685.5343474532
Товар27 787940.34 из 787940.3364260227
Товар28 719747.45 из 719747.4481560593
Товар29 839276.71 из 839276.7076206218
Товар30 171350.49 из 171350.49046382695
Товар31 774521.68 из 774521.6771186346
Товар32 769371.44 из 769371.4382454185
Товар33 243399.2 из 243399.19725691518
Товар34 818371.72 из 818371.7224263975
Товар35 263151.07 из 263151.0702352981
Товар36 676299.87 из 676299.8690587819
Товар37 687833.3 из 687833.2955874939
Товар38 112600.19 из 112600.19384111586
Товар39 499453.03 из 499453.031874757
Товар40 661994.23 из 661994.231672027
Товар41 225596.36 из 225596.36411810524
Товар42 958092.69 из 958092.6936240986
Товар43 681207.48 из 681207.4839389888
Товар44 221200.15 из 221200.14850950055
Товар45 200157.85 из 200157.84548828035
Товар46 286583.02 из 286583.0234027279
Товар47 577355.63 из 577355.6256299126
Товар48 333399.26 из 333399.2612021096
Товар49 345060.82 из 345060.8183317391
Товар50 240376.03 из 240376.03111233027
Товар51 680518.47 из 680518.4663040837
Товар52 463773.5 из 463773.4974714662
Товар53 603426.93 из 603426.9349440299
Товар54 585451.97 из 585451.9677209563
Товар55 818634.35 из 818634.3504291275
Товар56 171432.38 из 171432.37501094883
Товар57 495861.8 из 495861.8017951375
Товар58 103335.56 из 103335.55560669722
Товар59 545972.08 из 545972.0778357927
Товар60 937260.25 из 937260.2539286873
Товар61 799451.23 из 799451.2343092249
Товар62 417260.27 из 417260.2715133255
Товар63 120591.66 из 120591.66216110905
Товар64 358925.26 из 358925.2599059303
Товар65 855285.43 из 855285.4256332519
Товар66 347277.71 из 347277.713113735
Товар67 372653.73 из 372653.72638729645
Товар68 613341.49 из 613341.4875585965
Товар69 834008.56 из 834008.5598722058
Товар70 113592.22 из 113592.21629697594
Товар71 194557.76 из 194557.76160520766
Товар72 800146.21 из 800146.2055155531
Товар73 156028.23 из 156028.23439463944
Товар74 234383.66 из 234383.65903390953
Товар75 621669.05 из 621669.0491833334
Товар76 130080.2 из 130080.20308397856
Товар77 544095.08 из 544095.0768277377
Товар78 965060.27 из 965060.2690712278
Товар79 199402.61 из 199402.61458110923
Товар80 461476.24 из 461476.2426870921
Товар81 271535.89 из 271535.88928093534
Товар82 748673.35 из 748673.3531951199
Товар83 291829.24 из 291829.2366716161
Товар84 975848.71 из 975848.7145694873
Товар85 485652.47 из 485652.46757367696
Товар86 737538.76 из 737538.760422223
Товар87 189907.23 из 189907.22583928623
Товар88 109988.4 из 109988.40031527661
Товар89 984319.97 из 984319.965890239
Товар90 618869.2 из 618869.2020713241
Товар91 362838.35 из 362838.3468138749
Товар92 376860.57 из 376860.5702819198
Товар93 322127.98 из 322127.9759303717
Товар94 979302.1 из 979302.096856456
Товар95 820451.35 из 820451.3462925756
Товар96 189339.12 из 189339.12006266386
Товар97 193907.17 из 193907.17287269933
Товар98 748611.58 из 748611.581533799
Товар99 655311.7 из 655311.699386001
Товар100 796814.16 из 796814.15879224
Товар101 423842.35 из 423842.34665262274
Товар102 952255.41 из 952255.412758336
Товар103 581889.21 из 581889.2083885402
Товар104 722644.4 из 722644.4024255745
Товар105 451917.55 из 451917.5543063265
Товар106 785003.68 из 785003.6822073464
Товар107 357255.87 из 357255.87479735096
Товар108 951802.84 из 951802.8429228318
Товар109 374079.63 из 374079.6320391303
Товар110 424580.48 из 424580.48065054807
Товар111 281567.75 из 281567.7474588673
Товар112 298954.76 из 298954.75890279224
Товар113 432199.85 из 432199.85272635537
Товар114 581294.88 из 581294.8771369768
Товар115 173356.42 из 173356.4211978094
Товар116 706161.03 из 706161.0307623808
Товар117 605862.96 из 605862.960038322
Товар118 541192.3 из 541192.3019834808
Товар119 329730.36 из 329730.3633221672
Товар120 687708.83 из 687708.8338998506
Товар121 330420.68 из 330420.67869774863
Товар122 879502.95 из 879502.9486966063
Товар123 808008.66 из 808008.6649083216
Товар124 301853.22 из 301853.2235122584
Товар125 203009.27 из 203009.2664988107
Товар126 364144.01 из 364144.00981451105
Товар127 627419.97 из 627419.9685893131
Товар128 176633.14 из 176633.14050900837
Товар129 340103.11 из 340103.1123771363
Товар130 802280.96 из 802280.9580293891
Товар131 444502.26 из 444502.25690602284
Товар132 863546.48 из 863546.4821482579
Товар133 248756.34 из 248756.34119952025
Товар134 825107.12 из 825107.119392471
Товар135 395423.07 из 395423.0745651665
Товар136 708798.1 из 708798.0964840548
Товар137 831190.02 из 831190.0211546295
Товар138 661983.28 из 661983.2835724461
Товар139 290013.14 из 290013.1429606739
Товар140 262265.47 из 262265.4727330602
Товар141 892882.51 из 892882.5141660307
Товар142 155820.23 из 155820.2331731233
Товар143 701627.51 из 701627.5126059169
Товар144 805011.84 из 805011.8389548
Товар145 687742.73 из 687742.7342606192
Товар146 951532.86 из 951532.8624331568
Товар147 573488.76 из 573488.7620339128
Товар148 703435.55 из 703435.5461830014
Товар149 825949.83 из 825949.8310937249
Товар150 474429.05 из 474429.0545429463
Товар151 622619.97 из 622619.9695408016
Товар152 687086.01 из 687086.0058438272
Товар153 934332.89 из 934332.8887548604
Товар154 256323.93 из 256323.9250997613
Товар155 593558.24 из 593558.238855277
Товар156 949542.46 из 949542.4556368465
Товар157 771377.0 из 771376.9966740404
Товар158 786506.19 из 786506.1936954544
Товар159 628402.92 из 628402.9217995974
Товар160 231923.78 из 231923.77522107676
Товар161 831762.77 из 831762.7684432977
Товар162 414479.44 из 414479.4428540272
Товар163 523589.89 из 523589.8938237171
Товар164 258845.04 из 258845.04426821976
Товар165 100903.96 из 100903.96307715664
Товар166 163034.37 из 163034.36959932314
Товар167 653401.59 из 653401.590558145
Товар168 721290.15 из 721290.1491665429
Товар169 186619.43 из 186619.42698570632
Товар170 147015.39 из 147015.38818919464
Товар171 141790.47 из 141790.47086389558
Товар172 636990.77 из 636990.7669476826
Товар173 736812.17 из 736812.1654561599
Товар174 664545.77 из 664545.766602985
Товар175 102627.78 из 102627.77708906103
Товар176 786403.19 из 786403.1857887985
Товар177 358518.36 из 358518.36412963097
Товар178 635916.44 из 635916.4400603629
Товар179 485805.01 из 485805.0121598375
Товар180 468858.98 из 468858.9812794371
Товар181 556002.11 из 556002.1127324968
Товар182 973357.86 из 973357.8578341331
Товар183 974833.25 из 974833.2465184958
Товар184 242180.87 из 242180.86936195672
Товар185 322935.58 из 322935.57640718075
Товар186 748520.58 из 748520.5761595789
Товар187 496686.76 из 496686.76150578726
Товар188 325659.26 из 325659.26421606675
Товар189 996816.15 из 996816.1515029438
Товар190 765943.52 из 765943.5165366514
Товар191 464941.89 из 464941.89187614346
Товар192 784662.06 из 784662.0608521587
Товар193 599685.6 из 599685.5985937037
Товар194 555830.58 из 555830.582672107
Товар195 273451.6 из 273451.6046468464
Товар196 827005.41 из 827005.4104140169
Товар197 772435.84 из 772435.8386630347
Товар198 301427.21 из 301427.2057494812
Товар199 211326.19 из 211326.18839592487
Стоимость это и есть вес, то, что тут нулевая масса у товара только облегчает расчёт. То, что NP-полные задачи сводятся друг к другу известный факт.
Модель выше я привёл только для того чтобы показать, что не нужно изобретать гибридные алгоритмы, когда задача сводится к каноническому рюкзаку. D не всегда будет равно 0, но модель гарантирует, что оно будет максимально малым из всех возможных вариантов. Вам только остаётся принять результат или отбросить, если D больше заданной величины.
У вас там чистый рюкзак, только словесами окружён.
На скорую руку набросал модель.
import pulp as pl
import random as rnd
summa = 5000000.0
print('Сумма к которой стремимся, руб:', summa)
n = 20 # Количество наименований
# Кортеж из максимального числа товара для заказа и цены
goods = [(rnd.randint(20, 100), rnd.randint(100000, 1000000)/100) for i in range(n)]
print('Товарная номенклатура:', goods)
print()
# Объявляем модель
model = pl.LpProblem(name="Задача о госзакупках", sense=pl.LpMaximize)
# Подключаем решатель CBC
solver = pl.PULP_CBC_CMD(msg=True)
# Объявляем переменны
x = [pl.LpVariable(name=f'x{i:03}', cat='Integer', lowBound=0, upBound=goods[i][0]) for i in range(len(goods))]
# Целевая функция
model += pl.lpSum([x[i] * goods[i][1] for i in range(n)])
# Ограничение на сумму закупки
model += pl.lpSum([x[i] * goods[i][1] for i in range(n)]) <= summa
# Выводим модель
print(model)
# Находим решение
status = model.solve(solver)
if status == 1:
print('Фактически набрали, руб:', round(model.objective.value(), 2))
print('Заказать шт:')
for i, val in enumerate(model.variables()):
print(f'Товар{i} {int(val.value())} из {goods[i][0]} шт, на сумму: {round(int(val.value()) * goods[i][1], 2)}')
Cplex при размере матрицы более ста миллионов ненулевых значений начинает захлёбываться.
Cplex, захлёбываться. А вот CBC вытягивает. Не знаю, как они этого добиваются, сверхдлинной арифметикой или натуральными дробями или ещё как-то. Главное чтобы памяти хватало, и конечно большие матрицы это долго.
При этом, насколько я понимаю, для решения СЛАУ лучше сиплекса ничего нет.
А как же эллиптические кривые и метод внутренней точки? Гораздо быстрее симплекса, но они не подходят для целочисленного программирования.
Как я понял вы заставляете нейросеть искать корреляты среди параметров входного набора переменных и отбрасывать малозначимые переменные для ускорения расчёта решателем. Но как показывает практика решения MILP, такие переменные почти не дробятся и так. Выигрыш получается только на уменьшении симплекс матрицы, и довольно скромный.
Обычно для решения MILP используются решатели вроде Gurobi и Cplex.
Да эти коммерческие решатели очень хороши, но как альтернативу я бы предложил не SCIP, а CBC от COIN-OR. По крайней мере в моих задачах он в разы быстрее и точнее.
Ещё мне очень зашла библиотека scipy.optimize для Python, с методами:
Там есть некоторая проблема с точностью, но зато библиотека очень хороша за счёт разреженных матриц на задачах от 10к переменных.
И ещё, мне думается, что для задач распределения лучше подходит не линейное программирование, а Constraint programming. Хотя часто для последнего и используется линейные решатели.
то можно получить ещё 60% прироста производительности.
import random as rnd
import numpy as np
import time
def find_subset_sum(numbers: list[int], target: int) -> list[int]:
"""
Задача о сумме подмножеств натуральных чисел (Subset sum problem - SSP)
Решение с использованием алгоритма динамического программирования
"""
dp = np.zeros(target + 1, dtype='uint8' if len(numbers) < 256 else 'uint16')
dp[0] = len(numbers)
offset = 1
for i, val in enumerate(numbers):
offset += val
if offset > target + 1:
offset = target + 1
temp = dp[:offset-val].copy()
np.clip(temp, None, len(numbers) - i , temp)
np.maximum(dp[val:offset], temp, dp[val:offset])
if dp[target]:
break
if dp[target]:
break
if not dp[target]:
return []
subset = []
j = target
while j > 0:
i = numbers[len(numbers) - dp[j]]
subset.append(i)
j -= i
return subset[::-1]
n = 50
rnd.seed(1)
source = [rnd.randint(1000000, 9999999) for i in range(n)]
target_sum = sum(source) // 2
print('source:', source)
print('target_sum:', target_sum)
print()
start = time.time()
result = find_subset_sum(source, target_sum)
end = time.time()
elapsed_time = end - start
print(f"Execution time: {elapsed_time:.6f} seconds")
print('result:', sum(result), result)
Прирост скорости от 50% - 100% от базового решения.
Мне только так и не нравится, что по факту три прохода по массиву.
1) Копирование части массива
2) Присваивание значимых элементов
3) Максимизация
Как не бился, первые два прохода не объединяются в один. Точнее можно сделать через цикл, но он в двадцать раз медленнее получается, видимо векторизация отменяется.
Как понимаю на C можно в один проход сделать, но мне кажется всё равно медленнее будет чем текущая версия с векторизацией.
import random as rnd
import numpy as np
import time
def find_subset_sum(numbers: list, target: int):
dp = np.zeros(target + 1, dtype='uint8' if len(numbers) < 256 else 'uint16')
dp[0] = 1
offset = 1
for i, val in enumerate(numbers):
offset += val
if offset > target + 1:
offset = target + 1
temp = dp[:offset-val].copy()
temp[temp > 0] = len(numbers) - i
np.maximum(dp[val:offset], temp, dp[val:offset])
if dp[target]:
break
if not dp[target]:
return []
subset = []
j = target
while j > 0:
i = numbers[len(numbers) - dp[j]]
subset.append(i)
j -= i
return subset[::-1]
n = 50
rnd.seed(1)
source = [rnd.randint(1000000, 9999999) for i in range(n)]
target_sum = sum(source) // 2
print('source:', source)
print('target_sum:', target_sum)
print()
start = time.time()
result = find_subset_sum(source, target_sum)
end = time.time()
elapsed_time = end - start
print(f"Execution time: {elapsed_time:.6f} seconds")
print('result:', sum(result), result)
С последним вариантом неувязка вышла. Зато новая попытка в среднем 10% выигрыш по времени.
Основная идея в том, что не нужно трогать ту часть массива, которая остаётся неизменной на каждом этапе.
for i, val in enumerate(numbers):
temp = np.roll(dp, val).view()[val:]
temp[temp > 0] = len(numbers) - i
dp_slice = dp[val:]
np.maximum(dp_slice, temp, dp_slice)
if dp[target]:
break
for i, val in enumerate(numbers):
k = np.uint8(len(numbers) - i) if len(numbers) < 256 else np.uint16(len(numbers) - i)
temp = np.roll(dp, val)
temp[:val] = 0
np.maximum(dp, temp.astype(bool) * k, dp)
if dp[target]:
break
У меня ускорилось в два раза, так как мы убираем лишний проход по массиву.
Всякие максимумы, которые не факт что векторизованы.
np.maximum 100% векторизированна, там внутри должна быть интерпретация к PMAXUB/PMAXUW. А в зависимости от процессора там прирост может быть значительный.
И если вы будете его сравнивать с линейным решателем, то надо делить время на 10. Ведь решатель-то написан на каком-нибудь с++, а из питона вы лишь вызываете библиотеку
Ну это такой аргумент, numpy если я не ошибаюсь написан на том же си и так же использует SIMD векторизацию. Так что разница будет не столь значительна.
У вас в решении примерно это и хранится, только перевернутое - вы храните, сколько там единиц в столбце.
Не совсем так, я храню индекс числа в оригинальном массиве, в перевёрнутом виде. И оставляю больший индекс проходя функцией max (оставляем более старый) чтоб не затереть уже найденный маршрут. Мне такой подход напоминает алгоритм Дейкстры для поиска пути в графе.
Хотелось бы сравнить алгоритм с вашей реализацией по скорости.
Я долго сопротивлялся, но похоже вам удалось убедить меня в неправоте, за что вам большой респект. Один хороший контрпример решил дело.
Мне не остаётся ничего кроме, как проиндексировать биты dp, тогда восстановление идет всегда правильно. Памяти требует, как в оригинальном решении, при длине входного массива до 256 элементов, и в двое больше в ином случае.
import numpy as np
def find_subset_sum(numbers: list, target: int):
dp = np.zeros(target + 1, dtype='uint8' if len(numbers) < 256 else 'uint16')
dp[0] = len(numbers)
for i, val in enumerate(numbers):
temp = np.roll(dp, val)
temp[:val] = 0
temp[temp > 0] = len(numbers) - i
dp = np.maximum(dp, temp)
if dp[target]:
break
if not dp[target]:
return []
subset = []
j = target
while j > 0:
i = numbers[len(numbers) - dp[j]]
subset.append(i)
j -= i
return subset[::-1]
source = [2, 3, 3, 4, 52, 52, 100, 1000, 1000]
target_sum = 1108
print('source:', source)
print('target_sum:', target_sum)
print()
result = find_subset_sum(source, target_sum)
print('result:', sum(result), result)
Ну вот новый контрпример: ([2, 3, 3, 4, 52, 52, 100, 1000, 1000], 108) ...
Ну вот я добавил пару 1000 в массив и ваша эвристика сломалась.
Где же сломалась? Работает, проверьте исходные данные.
Еще раз, проблема в том, что можно получить ситуацию, что вам надо набрать 8, а у вас остались числа [2, 3, 3, 4]
Я понимаю резон в ваших словах, но и вы поймите, что смысл всех танцев как раз в том, чтобы исключить возможность выбора тех величин, что приведут к тупику в дальнейшем.
И да вы правы нужно доказать логически, а это не простая задача.
Благодарю Вас в вашем упорстве находить истину и желании помочь другим в этом же.
Действительно в моих первоначальных рассуждениях закралась ошибка: Если мы усекаем список просматриваемых чисел на первом этапе, то его и на втором этапе нужно усекать в том же объёме.
Однако, это не отменяет работоспособность самой идеи получения списка результата. Сортировка по возрастанию как раз и используется для того чтобы числа, которые могут состоять из нескольких меньших чисел утилизировались в первую очередь.
Я не убеждён, что и новый алгоритм не может содержать ошибки, но вы так категорично утверждаете, что решение в корне не верно, что вызывает желание понять почему.
На мой взгляд так как сложение - операция коммуникативная и ассоциативная, мы выстраиваем поле в рамках которого ищем результат, и не важно в каком порядке мы будем обходить это поле решений.
И ещё в процессе нашей дискуссии я исправил огрех, который не заметил сразу, после рола правые биты оказываются слева строки, а это иногда вносит ошибку. Потому выкладываю очередную версию, в которой все ваши контрпримеры вычисляются верно.
import bitstring as bit
def find_subset_sum(numbers: list, target: int):
numbers.sort()
dp = bit.BitArray(target + 1)
dp[0] = 1
count = -1
for i in numbers:
temp = dp.copy()
dp.ror(i)
dp.set(0, range(i))
dp |= temp
print('i:', i, dp.bin)
count += 1
if dp[target] == 1:
break
if not dp[target]:
return []
print()
subset = []
j = target
for i in numbers[count::-1]:
if j >= i and dp[j - i]:
print('i:', i, 'j:', j, '- берём')
subset.append(i)
j -= i
else:
print('i:', i, 'j:', j, '- не берём')
return subset[::-1]
source = [2, 3, 3, 4, 52, 52, 100]
target_sum = 108
print('source:', source)
print('target_sum:', target_sum)
print()
result = find_subset_sum(source, target_sum)
print('result:', sum(result), result)
Вам надо набрать 8, есть числа {2,3,3,4}. Первым шагом вы возьмете 4, ведь можно же набрать 4 всеми этими числами. И дальше все. Оставшиеся 4 вы никак из {2,3,3} не наберете.
А зачем вам использовать ДП для данной задачи, когда переменные не целые? Используйте симплекс метод, это и проще и быстрее. Конечно, у него есть проблема с точностью при float, но если использовать натуральные дроби в расчётах, то всё решаемо.
Ну как же в вашем примере это и есть рюкзак, только с единичной стоимостью за каждый товар :), те каждый товар имеет одинаковый вес (стоимость).
Если 100 это не единицы, а например общий вес в килограммах, тогда ещё проще. Просто поменяем тип переменных на нецелочисленный.
Это совсем просто, выполняет за секунду. Можно даже сделать минимальный порог, меньше которого нельзя набрать товара одного вида, например 1000 кг.
Код
Стоимость это и есть вес, то, что тут нулевая масса у товара только облегчает расчёт. То, что NP-полные задачи сводятся друг к другу известный факт.
Модель выше я привёл только для того чтобы показать, что не нужно изобретать гибридные алгоритмы, когда задача сводится к каноническому рюкзаку. D не всегда будет равно 0, но модель гарантирует, что оно будет максимально малым из всех возможных вариантов. Вам только остаётся принять результат или отбросить, если D больше заданной величины.
У вас там чистый рюкзак, только словесами окружён.
На скорую руку набросал модель.
Тестирование: несколько сотен номенклатур и миллионы рублей справляется за десяток секунд – минуту.
Cplex, захлёбываться. А вот CBC вытягивает. Не знаю, как они этого добиваются, сверхдлинной арифметикой или натуральными дробями или ещё как-то. Главное чтобы памяти хватало, и конечно большие матрицы это долго.
А как же эллиптические кривые и метод внутренней точки? Гораздо быстрее симплекса, но они не подходят для целочисленного программирования.
Отличная статья, мне импонирует ваш подход.
Как я понял вы заставляете нейросеть искать корреляты среди параметров входного набора переменных и отбрасывать малозначимые переменные для ускорения расчёта решателем. Но как показывает практика решения MILP, такие переменные почти не дробятся и так. Выигрыш получается только на уменьшении симплекс матрицы, и довольно скромный.
Да эти коммерческие решатели очень хороши, но как альтернативу я бы предложил не SCIP, а CBC от COIN-OR. По крайней мере в моих задачах он в разы быстрее и точнее.
Ещё мне очень зашла библиотека scipy.optimize для Python, с методами:
scipy.optimize.linprog
scipy.optimize.milp
Там есть некоторая проблема с точностью, но зато библиотека очень хороша за счёт разреженных матриц на задачах от 10к переменных.
И ещё, мне думается, что для задач распределения лучше подходит не линейное программирование, а Constraint programming. Хотя часто для последнего и используется линейные решатели.
Мне думается вы перепутали алгоритмы задача коммивояжёра и поиск пути.
Удалось, поделитесь результатами?
Было бы замечательно, если бы вы описали свой опыт в отдельной статье. С удовольствием читаю реальные истории.
И да, как вы описываете ограничения, очень похоже на задачу о рюкзаке. Она родственна текущей.
Оставлю тут для истории.
Если заменить сравнение:
на векторный аналог:
то можно получить ещё 60% прироста производительности.
А ларчик просто открывался!
Прирост скорости от 50% - 100% от базового решения.
Мне только так и не нравится, что по факту три прохода по массиву.
1) Копирование части массива
2) Присваивание значимых элементов
3) Максимизация
Как не бился, первые два прохода не объединяются в один. Точнее можно сделать через цикл, но он в двадцать раз медленнее получается, видимо векторизация отменяется.
Как понимаю на C можно в один проход сделать, но мне кажется всё равно медленнее будет чем текущая версия с векторизацией.
С последним вариантом неувязка вышла. Зато новая попытка в среднем 10% выигрыш по времени.
Основная идея в том, что не нужно трогать ту часть массива, которая остаётся неизменной на каждом этапе.
Попробуйте изменить на это:
У меня ускорилось в два раза, так как мы убираем лишний проход по массиву.
np.maximum 100% векторизированна, там внутри должна быть интерпретация к PMAXUB/PMAXUW. А в зависимости от процессора там прирост может быть значительный.
Ну это такой аргумент, numpy если я не ошибаюсь написан на том же си и так же использует SIMD векторизацию. Так что разница будет не столь значительна.
Не совсем так, я храню индекс числа в оригинальном массиве, в перевёрнутом виде. И оставляю больший индекс проходя функцией max (оставляем более старый) чтоб не затереть уже найденный маршрут. Мне такой подход напоминает алгоритм Дейкстры для поиска пути в графе.
Хотелось бы сравнить алгоритм с вашей реализацией по скорости.
Я долго сопротивлялся, но похоже вам удалось убедить меня в неправоте, за что вам большой респект. Один хороший контрпример решил дело.
Мне не остаётся ничего кроме, как проиндексировать биты dp, тогда восстановление идет всегда правильно. Памяти требует, как в оригинальном решении, при длине входного массива до 256 элементов, и в двое больше в ином случае.
Где же сломалась? Работает, проверьте исходные данные.
Я понимаю резон в ваших словах, но и вы поймите, что смысл всех танцев как раз в том, чтобы исключить возможность выбора тех величин, что приведут к тупику в дальнейшем.
И да вы правы нужно доказать логически, а это не простая задача.
Благодарю Вас в вашем упорстве находить истину и желании помочь другим в этом же.
Действительно в моих первоначальных рассуждениях закралась ошибка: Если мы усекаем список просматриваемых чисел на первом этапе, то его и на втором этапе нужно усекать в том же объёме.
Однако, это не отменяет работоспособность самой идеи получения списка результата. Сортировка по возрастанию как раз и используется для того чтобы числа, которые могут состоять из нескольких меньших чисел утилизировались в первую очередь.
Я не убеждён, что и новый алгоритм не может содержать ошибки, но вы так категорично утверждаете, что решение в корне не верно, что вызывает желание понять почему.
На мой взгляд так как сложение - операция коммуникативная и ассоциативная, мы выстраиваем поле в рамках которого ищем результат, и не важно в каком порядке мы будем обходить это поле решений.
И ещё в процессе нашей дискуссии я исправил огрех, который не заметил сразу, после рола правые биты оказываются слева строки, а это иногда вносит ошибку. Потому выкладываю очередную версию, в которой все ваши контрпримеры вычисляются верно.
Обратите внимание на условие:
Оно заранее завершает процесс заполнения dp, и исключает во многом те ситуации, что вы описывали в предыдущем ответе.
Это не так! Проиллюстрирую:
Так понимаю достаточно сделать:
numbers.sort()первым шагом функции.Поскольку обход цикла идёт с конца списка, проблема полностью устраняется.