{"id":373245,"date":"2024-05-21T05:31:44","date_gmt":"2024-05-21T05:31:44","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=373245"},"modified":"-0001-11-30T00:00:00","modified_gmt":"2024-05-21T05:31:44","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=373245","title":{"rendered":"\u0417\u0430\u0434\u0430\u0447\u0430 \u043e \u0441\u0443\u043c\u043c\u0435 \u043f\u043e\u0434\u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432<\/span>"},"content":{"rendered":"
<\/div>\n
\n
\n
\n
\n
<\/figure>\n

\u0417\u0430\u0434\u0430\u0447\u0430 \u043e \u0441\u0443\u043c\u043c\u0435 \u043f\u043e\u0434\u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432<\/a> \u0432 \u043e\u0431\u0449\u0435\u0439 \u0444\u043e\u0440\u043c\u0443\u043b\u0438\u0440\u043e\u0432\u043a\u0435 \u0437\u0432\u0443\u0447\u0438\u0442 \u0442\u0430\u043a: <\/p>\n

\u0421\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e S \u0447\u0438\u0441\u0435\u043b. \u0412\u043e\u043f\u0440\u043e\u0441 \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0432 \u0442\u043e\u043c, \u0431\u0443\u0434\u0435\u0442 \u043b\u0438 \u0441\u0443\u043c\u043c\u0430 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u043f\u043e\u0434\u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430 \u043e\u0442 S \u0440\u0430\u0432\u043d\u0430 \u0437\u0430\u0434\u0430\u043d\u043d\u043e\u043c\u0443 \u0447\u0438\u0441\u043b\u0443 \u0422.<\/em> <\/p>\n

\u0418\u0437\u0432\u0435\u0441\u0442\u043d\u043e, \u0447\u0442\u043e \u0434\u0430\u043d\u043d\u0430\u044f \u0437\u0430\u0434\u0430\u0447\u0430 NP-\u043f\u043e\u043b\u043d\u0430\u044f.<\/p>\n

\u041c\u044b \u0431\u0443\u0434\u0435\u043c \u0440\u0435\u0448\u0430\u0442\u044c \u044d\u043a\u0432\u0438\u0432\u0430\u043b\u0435\u043d\u0442\u043d\u0443\u044e \u0437\u0430\u0434\u0430\u0447\u0443, \u0433\u0434\u0435 \u0432\u0441\u0435 \u0447\u0438\u0441\u043b\u0430 \u044f\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u043d\u0430\u0442\u0443\u0440\u0430\u043b\u044c\u043d\u044b\u043c\u0438.<\/p>\n

\u0427\u0430\u0441\u0442\u043d\u044b\u043c \u0441\u043b\u0443\u0447\u0430\u0435\u043c \u0437\u0430\u0434\u0430\u0447\u0438 \u043e \u0441\u0443\u043c\u043c\u0435 \u043f\u043e\u0434\u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0437\u0430\u0434\u0430\u0447\u0430 \u0440\u0430\u0437\u0431\u0438\u0435\u043d\u0438\u044f \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430 \u0447\u0438\u0441\u0435\u043b<\/a>:<\/p>\n

\u041c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u0447\u0438\u0441\u0435\u043b S \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0440\u0430\u0437\u0431\u0438\u0442\u044c \u043d\u0430 \u0434\u0432\u0430 \u043f\u043e\u0434\u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430 S1 \u0438 S2, \u0433\u0434\u0435 \u0441\u0443\u043c\u043c\u0430 S1 \u0440\u0430\u0432\u043d\u0430 \u0441\u0443\u043c\u043c\u0435 S2.<\/em> <\/p>\n

(\u041e\u0442 \u0437\u0430\u0434\u0430\u0447\u0438 \u043e \u0441\u0443\u043c\u043c\u0435 \u043f\u043e\u0434\u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432 \u0442\u0435\u043a\u0443\u0449\u0430\u044f \u043e\u0442\u043b\u0438\u0447\u0430\u0435\u0442\u0441\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u0442\u0435\u043c, \u0447\u0442\u043e T = Sum(S1) \/ 2 = Sum(S2) \/ 2<\/em>)<\/p>\n

\u0425\u043e\u0447\u0443 \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0438\u0442\u044c \u0432\u0430\u043c \u043f\u0440\u043e\u0441\u0442\u043e\u0439 \u0438 \u044d\u043b\u0435\u0433\u0430\u043d\u0442\u043d\u044b\u0439 \u0441\u043f\u043e\u0441\u043e\u0431 \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0431\u044b\u0441\u0442\u0440\u043e\u0433\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u043e\u0431\u0435\u0438\u0445 \u0437\u0430\u0434\u0430\u0447 \u043c\u0435\u0442\u043e\u0434\u043e\u043c \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u043e\u0433\u043e \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0433\u043e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f<\/a> (\u0426\u041b\u041f). \u041c\u044b \u043f\u043e\u043b\u0443\u0447\u0438\u043c \u043d\u0435 \u0442\u043e\u043b\u044c\u043a\u043e \u0442\u043e\u0447\u043d\u044b\u0439 \u043e\u0442\u0432\u0435\u0442 \u043d\u0430 \u0432\u043e\u043f\u0440\u043e\u0441, \u043d\u043e \u0438 \u043d\u0430\u0439\u0434\u0451\u043c \u0438\u0441\u043a\u043e\u043c\u043e\u0435 \u043f\u043e\u0434\u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e.<\/p>\n

\u0418 \u0442\u0430\u043a, \u0443 \u043d\u0430\u0441 \u0435\u0441\u0442\u044c \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e S<\/em> \u043d\u0430\u0442\u0443\u0440\u0430\u043b\u044c\u043d\u044b\u0445 \u0447\u0438\u0441\u0435\u043b:<\/p>\n

\"S<\/p>\n

\u041d\u0430\u043c \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u043e\u0442\u0432\u0435\u0442\u0438\u0442\u044c \u043d\u0430 \u0432\u043e\u043f\u0440\u043e\u0441: \u0412\u043e\u0437\u043c\u043e\u0436\u043d\u043e \u043b\u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0434\u0430\u043d\u043d\u043e\u0433\u043e \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430 \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u0441\u0443\u043c\u043c\u0443 \u0440\u0430\u0432\u043d\u0443\u044e T<\/em>?<\/p>\n

\u0414\u043b\u044f \u043d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u044f \u043e\u0442\u0432\u0435\u0442\u0430 \u043d\u0443\u0436\u043d\u043e \u0440\u0435\u0448\u0438\u0442\u044c \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0435 \u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0435: <\/p>\n

\"\\sum_{i=1}^{n}S_{i}*X_{i}=T;<\/p>\n

\u0415\u0441\u043b\u0438 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0431\u0443\u0434\u0435\u0442 \u043d\u0430\u0439\u0434\u0435\u043d\u043e, \u0442\u043e \u043e\u0442\u0432\u0435\u0442 \u043d\u0430 \u0432\u043e\u043f\u0440\u043e\u0441 \u043f\u043e\u043b\u043e\u0436\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0439, \u0435\u0441\u043b\u0438 \u0436\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u043d\u0435\u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e, \u0442\u043e \u043e\u0442\u0440\u0438\u0446\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0439. \u0415\u0441\u043b\u0438 \u0440\u0435\u0448\u0435\u043d\u0438\u0439 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e, \u043d\u0430\u0441 \u0443\u0441\u0442\u0440\u043e\u0438\u0442 \u043b\u044e\u0431\u043e\u0435.<\/p>\n

\u0418\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f Python \u0438 \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0443 PuLP<\/a>, \u043f\u0440\u043e\u0438\u043b\u043b\u044e\u0441\u0442\u0440\u0438\u0440\u0443\u0435\u043c \u043d\u0430 \u043f\u0440\u0438\u043c\u0435\u0440\u0435.<\/p>\n

import pulp as pl src = [59, 63, 15, 43, 75, 72, 61, 48, 71, 55] n = len(src)  # \u0418\u0441\u043a\u043e\u043c\u043e\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 val = sum(src) \/\/ 2 # \u041e\u0431\u044a\u044f\u0432\u043b\u044f\u0435\u043c \u043c\u043e\u0434\u0435\u043b\u044c model = pl.LpProblem(name=\"Subset sum problem\", sense=pl.LpMinimize)        # \u041f\u043e\u0434\u043a\u043b\u044e\u0447\u0430\u0435\u043c \u0440\u0435\u0448\u0430\u0442\u0435\u043b\u044c CBC solver = pl.PULP_CBC_CMD(msg=True) # \u041e\u0431\u044a\u044f\u0432\u043b\u044f\u0435\u043c \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0435 x = [pl.LpVariable(name=f'x{i:05}', cat='Binary') for i in range(n)]     # \u0426\u0435\u043b\u0435\u0432\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f model += pl.lpSum([x[i] for i in range(n)])     # \u041e\u0441\u043d\u043e\u0432\u043d\u043e\u0435 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435 model += pl.lpSum([x[i] * src[i] for i in range(n)]) == val  print(model)<\/code><\/pre>\n
\u0412 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0435 \u043c\u044b \u043f\u043e\u043b\u0443\u0447\u0438\u043c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0443\u044e \u043c\u043e\u0434\u0435\u043b\u044c \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0433\u043e \u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f:<\/p>\n
Subset sum problem: MINIMIZE 1*x00000 + 1*x00001 + 1*x00002 + 1*x00003 + 1*x00004 + 1*x00005  + 1*x00006 + 1*x00007 + 1*x00008 + 1*x00009 + 0 SUBJECT TO _C1: 59 x00000 + 63 x00001 + 15 x00002 + 43 x00003 + 75 x00004 + 72 x00005  + 61 x00006 + 48 x00007 + 71 x00008 + 55 x00009 = 281 VARIABLES 0 <= x00000 <= 1 Integer 0 <= x00001 <= 1 Integer 0 <= x00002 <= 1 Integer 0 <= x00003 <= 1 Integer 0 <= x00004 <= 1 Integer 0 <= x00005 <= 1 Integer 0 <= x00006 <= 1 Integer 0 <= x00007 <= 1 Integer 0 <= x00008 <= 1 Integer 0 <= x00009 <= 1 Integer<\/code><\/pre>\n
\u0417\u0430\u043f\u0443\u0441\u043a\u0430\u0435\u043c \u0440\u0435\u0448\u0430\u0442\u0435\u043b\u044c \u0438 \u0432\u044b\u0432\u043e\u0434\u0438\u043c \u0440\u0435\u0448\u0435\u043d\u0438\u0435<\/p>\n
# \u041d\u0430\u0445\u043e\u0434\u0438\u043c \u0440\u0435\u0448\u0435\u043d\u0438\u0435 status = model.solve(solver) res = [] if status == 1:         for j, v in enumerate(model.variables()):         if v.value() > 0:             res.append(src[j]) print('\u0420\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442:', sum(res), res)  \u0420\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442: 281 [63, 75, 72, 71]<\/code><\/pre>\n
\u0427\u0442\u043e \u0438 \u0442\u0440\u0435\u0431\u043e\u0432\u0430\u043b\u043e\u0441\u044c \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c.<\/p>\n
\u041e\u0434\u043d\u0430\u043a\u043e, \u0447\u0435\u043c \u0431\u043e\u043b\u044c\u0448\u0435 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0435 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u0438 \u0447\u0435\u043c \u043a\u0440\u0443\u043f\u043d\u0435\u0435 \u0432\u0435\u043b\u0438\u0447\u0438\u043d\u044b \u0435\u0433\u043e \u0441\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u044e\u0449\u0438\u0435, \u0442\u0435\u043c \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u0435\u0435 \u0438\u0434\u0451\u0442 \u043f\u043e\u0438\u0441\u043a \u0440\u0435\u0448\u0435\u043d\u0438\u044f. <\/p>\n
\u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440 \u0434\u043b\u044f \u043f\u043e\u0438\u0441\u043a\u0430 \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0433\u043e \u0441\u043f\u0438\u0441\u043a\u0430 \u0438\u0437 24 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u043f\u043e\u0442\u0440\u0435\u0431\u043e\u0432\u0430\u043b\u043e\u0441\u044c \u043f\u043e\u0440\u044f\u0434\u043a\u0430 \u0434\u0432\u0430\u0434\u0446\u0430\u0442\u0438 \u0441\u0435\u043a\u0443\u043d\u0434.<\/p>\n
source = [1485498, 1643002, 1391445, 1280110, 1145269, 1195187, 1908655, 1709512,            1006747, 1354760, 1527205, 1486247, 1941933, 1634072, 1084740, 1350249,            1581194, 1981871, 1646604, 1734106, 1042882, 1763564, 1397430, 1177643]<\/code><\/pre>\n
\u0412\u043e\u0437\u043c\u043e\u0436\u043d\u043e \u043b\u0438 \u043a\u0430\u043a-\u0442\u043e \u0443\u0441\u043a\u043e\u0440\u0438\u0442\u044c \u043f\u0440\u043e\u0446\u0435\u0441\u0441 \u043d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u044f? <\/p>\n
\u0418\u043c\u0435\u043d\u043d\u043e \u043e\u0442\u0432\u0435\u0442 \u043d\u0430 \u044d\u0442\u043e\u0442 \u0432\u043e\u043f\u0440\u043e\u0441 \u0438 \u043f\u043e\u0431\u0443\u0434\u0438\u043b \u043c\u0435\u043d\u044f \u043d\u0430\u043f\u0438\u0441\u0430\u0442\u044c \u0434\u0430\u043d\u043d\u044b\u0439 \u043f\u043e\u0441\u0442. \u0422\u0430\u043a \u043a\u0430\u043a \u0437\u0430\u0434\u0430\u0447\u0430 \u0426\u041b\u041f \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f NP-\u0441\u043b\u043e\u0436\u043d\u043e\u0439, \u0442\u043e \u0441\u0447\u0438\u0442\u0430\u0435\u0442\u0441\u044f \u0447\u0442\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043d\u0430\u0445\u043e\u0434\u0438\u0442 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u044d\u043a\u0441\u043f\u043e\u043d\u0435\u043d\u0446\u0438\u0430\u043b\u044c\u043d\u044b\u043c \u043e\u0442 \u0447\u0438\u0441\u043b\u0430 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432.<\/p>\n
\u041f\u043e\u044d\u0442\u043e\u043c\u0443 \u043f\u0440\u0435\u0434\u043b\u0430\u0433\u0430\u044e «\u0435\u0441\u0442\u044c \u0441\u043b\u043e\u043d\u0430 \u043f\u043e \u043a\u0443\u0441\u043e\u0447\u043a\u0430\u043c» (\u0440\u0430\u0437\u0431\u0438\u0442\u044c \u0441\u043b\u043e\u0436\u043d\u0443\u044e \u0437\u0430\u0434\u0430\u0447\u0443 \u043d\u0430 \u0431\u043e\u043b\u0435\u0435 \u043f\u0440\u043e\u0441\u0442\u044b\u0435 \u0438 \u043c\u0435\u043d\u0435\u0435 \u043e\u0431\u044a\u0435\u043c\u043d\u044b\u0435 \u0447\u0430\u0441\u0442\u0438). <\/p>\n
\u041c\u044b \u0440\u0430\u0437\u0434\u0435\u043b\u0438\u043c \u0437\u0430\u0434\u0430\u0447\u0443 \u043d\u0430 \u0440\u044f\u0434 \u0437\u0430\u0434\u0430\u0447 \u043c\u0435\u043d\u044c\u0448\u0435\u0439 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u0438 \u0432\u0432\u0435\u0434\u0435\u043d\u0438\u0435\u043c \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0445 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0439 \u0432 \u043c\u043e\u0434\u0435\u043b\u044c, \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u043c \u0438\u0445 \u043f\u043e \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438. \u0410 \u0437\u0430\u0442\u0435\u043c \u0432\u044b\u0431\u0435\u0440\u0435\u043c \u043e\u0434\u043d\u043e \u0438\u0437 \u0434\u043e\u043f\u0443\u0441\u0442\u0438\u043c\u044b\u0445 \u0440\u0435\u0448\u0435\u043d\u0438\u0439, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u0438 \u0431\u0443\u0434\u0435\u0442 \u0441\u0447\u0438\u0442\u0430\u0442\u044c\u0441\u044f \u0438\u0441\u043a\u043e\u043c\u044b\u043c.<\/p>\n
\u0414\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0435 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435 \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0439 \u0438\u0437 \u043f\u043e\u0434\u0437\u0430\u0434\u0430\u0447 \u0431\u0443\u0434\u0435\u0442 \u0437\u0432\u0443\u0447\u0430\u0442\u044c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c: \u0414\u043b\u044f \u043d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u044f \u0438\u0441\u043a\u043e\u043c\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 T<\/em> \u043d\u0430\u043c \u043f\u043e\u043d\u0430\u0434\u043e\u0431\u044f\u0442\u0441\u044f \u0440\u043e\u0432\u043d\u043e Y<\/em> \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432. \u0414\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0439 \u0438\u0437 \u043f\u043e\u0434\u0437\u0430\u0434\u0430\u0447 \u043c\u044b \u0431\u0443\u0434\u0435\u043c \u0431\u0440\u0430\u0442\u044c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 Y<\/em> \u0438\u0437 \u0441\u043f\u0438\u0441\u043a\u0430.<\/p>\n
Y<\/em> = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24]<\/p>\n
\"\u041c\u0435\u0442\u0430\u0444\u043e\u0440\u0430:<\/p>\n
\u041c\u0435\u0442\u0430\u0444\u043e\u0440\u0430: \u0434\u043b\u044f \u0443\u043f\u043e\u0442\u0440\u0435\u0431\u043b\u0435\u043d\u0438\u044f \u0432 \u043f\u0438\u0449\u0443 \u0440\u0430\u0437\u0440\u0435\u0437\u0430\u043d\u043d\u044b\u0439 \u043d\u0430 \u043b\u043e\u043c\u0442\u0438\u043a\u0438 \u0431\u0430\u0442\u043e\u043d \u0441\u044a\u0435\u0441\u0442\u044c \u043f\u0440\u043e\u0449\u0435, \u0447\u0435\u043c \u0440\u0430\u0437\u0436\u0435\u0432\u0430\u0442\u044c \u0435\u0433\u043e \u0446\u0435\u043b\u0438\u043a\u043e\u043c.<\/figcaption><\/div>\n<\/figure>\n
\u041e\u0431\u0440\u0430\u0442\u0438\u0442\u0435 \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u0435, \u043a\u0430\u043a \u0438 \u0432 \u043c\u0435\u0442\u0430\u0444\u043e\u0440\u0435 \u0441 \u0431\u0430\u0442\u043e\u043d\u043e\u043c, \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u043f\u043e \u043a\u0440\u0430\u044f\u043c \u0431\u0443\u0434\u0443\u0442 \u043c\u0435\u043d\u044c\u0448\u0435\u0433\u043e \u0440\u0430\u0437\u043c\u0435\u0440\u0430, \u043f\u043e\u0442\u043e\u043c\u0443 \u043d\u0430\u0445\u043e\u0434\u044f\u0442\u0441\u044f \u0431\u044b\u0441\u0442\u0440\u0435\u0435. \u041f\u0440\u0435\u0434\u043b\u0430\u0433\u0430\u044e \u043d\u0430\u0447\u0438\u043d\u0430\u0442\u044c \u0438\u043c\u0435\u043d\u043d\u043e \u0441 \u043a\u0440\u0430\u0451\u0432, \u0442\u0430\u043a \u043a\u0430\u043a \u043d\u0430\u0439\u0434\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u043c\u043e\u0436\u043d\u043e \u043e\u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u044c \u043f\u043e\u0438\u0441\u043a \u043e\u0441\u0442\u0430\u043b\u044c\u043d\u044b\u0445 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0445 \u0440\u0435\u0448\u0435\u043d\u0438\u0439, \u044d\u043a\u043e\u043d\u043e\u043c\u044f \u0432\u0440\u0435\u043c\u044f.<\/p>\n
Y<\/em> = [1, 24, 2, 23, 3, 22, 4, 21, 5, 20, 6, 19, 7, 18, 8, 17, 9, 16, 10, 15, 11, 14, 12, 13]<\/p>\n
\u0427\u0438\u0442\u0430\u0442\u044c \u043d\u0443\u0436\u043d\u043e \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c: \u0421\u0443\u043c\u043c\u0430 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 \u043b\u044e\u0431\u044b\u0445 Y<\/em> \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430 \u0434\u043e\u043b\u0436\u043d\u0430 \u0431\u044b\u0442\u044c \u0440\u0430\u0432\u043d\u0430 \u0438\u0441\u043a\u043e\u043c\u043e\u043c\u0443 T<\/em>, \u0433\u0434\u0435 Y<\/em> \u2013 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0438\u0437 \u0441\u043f\u0438\u0441\u043a\u0430 \u0432\u044b\u0448\u0435.<\/p>\n
\u0420\u0435\u0448\u0430\u044f \u043f\u043e\u0434\u0437\u0430\u0434\u0430\u0447\u0438 \u043f\u043e \u0442\u0430\u043a\u043e\u0439 \u0441\u0445\u0435\u043c\u0435, \u043c\u044b \u043d\u0430\u0439\u0434\u0451\u043c \u043e\u0442\u0432\u0435\u0442 \u0431\u044b\u0441\u0442\u0440\u0435\u0435, \u0447\u0435\u043c \u0440\u0435\u0448\u0430\u044f \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b\u044c\u043d\u0443\u044e \u0437\u0430\u0434\u0430\u0447\u0443. \u0422\u0430\u043a \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440 \u0434\u043b\u044f \u043d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0434\u043b\u044f \u0440\u044f\u0434\u0430 \u0432\u044b\u0448\u0435, \u043f\u043e\u043d\u0430\u0434\u043e\u0431\u0438\u0442\u0441\u044f \u043d\u0435\u043c\u043d\u043e\u0433\u0438\u043c \u0431\u043e\u043b\u0435\u0435 \u0434\u0432\u0443\u0445 \u0441\u0435\u043a\u0443\u043d\u0434.<\/p>\n
\u041e\u0442\u043b\u0438\u0447\u0438\u0435 \u043e\u0442 \u043a\u043e\u0434\u0430 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0435\u0433\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0431\u0443\u0434\u0435\u0442 \u0442\u043e\u043b\u044c\u043a\u043e \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u043c\u044b \u0431\u0443\u0434\u0435\u043c \u0438\u0441\u043a\u0430\u0442\u044c \u043d\u0435 \u043e\u0434\u043d\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u0435, \u0430 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e:<\/p>\n
loop = list(range(1, n + 1)) loop = [loop.pop(0) if i % 2 == 0 else loop.pop(-1) for i in range(n)] for val in loop:     # \u0423\u0441\u0442\u0430\u043d\u0430\u0432\u043b\u0438\u0432\u0430\u0435\u043c \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0435 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435 \u0448\u0430\u0433\u0430 \u0446\u0438\u043a\u043b\u0430     model.constraints['Y'] = pl.lpSum([x[j] for j in range(n)]) == val      print(model)          # \u041d\u0430\u0445\u043e\u0434\u0438\u043c \u0440\u0435\u0448\u0435\u043d\u0438\u0435     status = model.solve(solver)       if status == 1:         res = []         for j, v in enumerate(model.variables()):             if v.value() > 0:                 res.append(src[j])             return res return []<\/code><\/pre>\n
\u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c \u043c\u044b \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e \u0431\u0443\u0434\u0435\u043c \u0441\u0442\u0440\u043e\u0438\u0442\u044c \u0440\u044f\u0434 \u043c\u043e\u0434\u0435\u043b\u0435\u0439 \u0438 \u043f\u044b\u0442\u0430\u0442\u044c\u0441\u044f \u043d\u0430\u0439\u0442\u0438 \u0440\u0435\u0448\u0435\u043d\u0438\u0435.<\/p>\n
Subset sum problem: MINIMIZE 1*x00000 + 1*x00001 + 1*x00002 + 1*x00003 + 1*x00004 + 1*x00005 + 1*x00006  + 1*x00007 + 1*x00008 + 1*x00009 + 1*x00010 + 1*x00011 + 1*x00012 + 1*x00013  + 1*x00014 + 1*x00015 + 1*x00016 + 1*x00017 + 1*x00018 + 1*x00019 + 1*x00020  + 1*x00021 + 1*x00022 + 1*x00023 + 0 SUBJECT TO _C1: 1485498 x00000 + 1643002 x00001 + 1391445 x00002 + 1280110 x00003  + 1145269 x00004 + 1195187 x00005 + 1908655 x00006 + 1709512 x00007  + 1006747 x00008 + 1354760 x00009 + 1527205 x00010 + 1486247 x00011  + 1941933 x00012 + 1634072 x00013 + 1084740 x00014 + 1350249 x00015  + 1581194 x00016 + 1981871 x00017 + 1646604 x00018 + 1734106 x00019  + 1042882 x00020 + 1763564 x00021 + 1397430 x00022 + 1177643 x00023  = 17734962  Y: x00000 + x00001 + x00002 + x00003 + x00004 + x00005 + x00006 + x00007  + x00008 + x00009 + x00010 + x00011 + x00012 + x00013 + x00014 + x00015  + x00016 + x00017 + x00018 + x00019 + x00020 + x00021 + x00022 + x00023 = 1  VARIABLES 0 <= x00000 <= 1 Integer 0 <= x00001 <= 1 Integer 0 <= x00002 <= 1 Integer 0 <= x00003 <= 1 Integer 0 <= x00004 <= 1 Integer 0 <= x00005 <= 1 Integer 0 <= x00006 <= 1 Integer 0 <= x00007 <= 1 Integer 0 <= x00008 <= 1 Integer 0 <= x00009 <= 1 Integer 0 <= x00010 <= 1 Integer 0 <= x00011 <= 1 Integer 0 <= x00012 <= 1 Integer 0 <= x00013 <= 1 Integer 0 <= x00014 <= 1 Integer 0 <= x00015 <= 1 Integer 0 <= x00016 <= 1 Integer 0 <= x00017 <= 1 Integer 0 <= x00018 <= 1 Integer 0 <= x00019 <= 1 Integer 0 <= x00020 <= 1 Integer 0 <= x00021 <= 1 Integer 0 <= x00022 <= 1 Integer 0 <= x00023 <= 1 Integer<\/code><\/pre>\n
\u041e\u0442\u043b\u0438\u0447\u0430\u0442\u044c\u0441\u044f \u043e\u043d\u0438 \u0431\u0443\u0434\u0443\u0442 \u0442\u043e\u043b\u044c\u043a\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435\u043c \u043f\u0440\u0430\u0432\u043e\u0439 \u0447\u0430\u0441\u0442\u0438 \u0440\u0430\u0432\u0435\u043d\u0441\u0442\u0432\u0430 \u0432 18 \u0441\u0442\u0440\u043e\u043a\u0435.<\/p>\n
\u041f\u043e\u0434\u0445\u043e\u0434 \u043e\u043f\u0438\u0441\u0430\u043d\u043d\u044b\u0439 \u0432 \u0440\u0430\u0431\u043e\u0442\u0435 \u0445\u043e\u0442\u044c \u0438 \u043d\u0435 \u0438\u0434\u0435\u0430\u043b\u044c\u043d\u044b\u0439, \u043d\u043e \u0432\u043f\u043e\u043b\u043d\u0435 \u0440\u0430\u0431\u043e\u0447\u0438\u0439. \u041d\u0435\u0441\u043c\u043e\u0442\u0440\u044f \u043d\u0430 \u0442\u043e, \u0447\u0442\u043e \u0441\u0430\u043c\u0430 \u0437\u0430\u0434\u0430\u0447\u0430 NP-\u0441\u043b\u043e\u0436\u043d\u0430, \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u044c \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0434\u043b\u044f \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432 \u043e\u0442 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u0438\u0445 \u0434\u0435\u0441\u044f\u0442\u043a\u043e\u0432 \u0434\u043e \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u0438\u0445 \u0441\u043e\u0442\u0435\u043d \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0432 \u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u0438 \u043e\u0442 \u0438\u0441\u0445\u043e\u0434\u043d\u044b\u0445 \u0434\u0430\u043d\u043d\u044b\u0445.<\/p>\n
\n\u041f\u0440\u0438\u043c\u0435\u0447\u0430\u043d\u0438\u0435<\/summary>\n
\n
\u041e\u0442\u0434\u0435\u043b\u044c\u043d\u043e \u0441\u0442\u043e\u0438\u0442 \u043e\u0442\u043c\u0435\u0442\u0438\u0442\u044c, \u0447\u0442\u043e \u043d\u0435 \u043a\u0430\u0436\u0434\u044b\u0439 \u0440\u0435\u0448\u0430\u0442\u0435\u043b\u044c \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u0445 \u043b\u0438\u043d\u0435\u0439\u043d\u044b\u0445 \u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0439 \u0441\u043f\u043e\u0441\u043e\u0431\u0435\u043d \u0442\u043e\u0447\u043d\u043e \u0440\u0435\u0448\u0438\u0442\u044c \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u0443\u044e \u043b\u0438\u043d\u0435\u0439\u043d\u0443\u044e \u0437\u0430\u0434\u0430\u0447\u0443. \u0418\u0437-\u0437\u0430 \u043e\u0441\u043e\u0431\u0435\u043d\u043d\u043e\u0441\u0442\u0435\u0439 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u043c\u043d\u043e\u0433\u0438\u0435 \u0440\u0435\u0448\u0430\u0442\u0435\u043b\u0438 \u043f\u0440\u0438\u0441\u0443\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0435 \u043d\u0430 \u0440\u044b\u043d\u043a\u0435 \u0438\u043c\u0435\u044e\u0442 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u0443\u044e \u043f\u043e\u0433\u0440\u0435\u0448\u043d\u043e\u0441\u0442\u044c \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0439, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043d\u0435\u0437\u043d\u0430\u0447\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0432\u043b\u0438\u044f\u0435\u0442 \u043d\u0430 \u043a\u043e\u043d\u0435\u0447\u043d\u044b\u0439 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u0432 \u0442\u0438\u043f\u043e\u0432\u044b\u0445 \u0437\u0430\u0434\u0430\u0447\u0430\u0445. \u041d\u043e \u0432 \u0434\u0430\u043d\u043d\u043e\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0435, \u0440\u0430\u0437 \u0443\u0436 \u043c\u044b \u0433\u043e\u0432\u043e\u0440\u0438\u043c \u043f\u0440\u043e \u0442\u043e\u0447\u043d\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435<\/strong>, \u043e\u0441\u043e\u0431\u0435\u043d\u043d\u043e \u043f\u0440\u0438 \u0431\u043e\u043b\u044c\u0448\u0438\u0445 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f\u0445 \u0432\u0445\u043e\u0434\u043d\u044b\u0445 \u0434\u0430\u043d\u043d\u044b\u0445, \u0432\u044b\u0431\u043e\u0440 \u0440\u0435\u0448\u0430\u0442\u0435\u043b\u044f \u043c\u043e\u0436\u0435\u0442 \u043a\u0430\u0442\u0430\u0441\u0442\u0440\u043e\u0444\u0438\u0447\u0435\u0441\u043a\u0438 \u043f\u043e\u0432\u043b\u0438\u044f\u0442\u044c \u043d\u0430 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442.<\/p>\n
\u0412 \u043c\u043e\u0438\u0445 \u0442\u0435\u0441\u0442\u0430\u0445 \u0442\u043e\u043b\u044c\u043a\u043e CBC <\/a>\u043e\u0442 COIN-OR Foundation \u0438 OR-Tools<\/a> \u043e\u0442 Google, \u0441\u043f\u0440\u0430\u0432\u0438\u043b\u0438\u0441\u044c \u0441 \u0434\u0430\u043d\u043d\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0435\u0439 \u0432\u0435\u0440\u043d\u043e.<\/p>\n<\/div>\n<\/details>\n
\u0417\u0430\u043a\u043b\u044e\u0447\u0435\u043d\u0438\u0435: <\/p>\n
\u041d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0437\u0430\u0434\u0430\u0447\u0438 \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u043e\u0433\u043e \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0433\u043e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u043c\u043e\u0436\u043d\u043e \u0440\u0435\u0448\u0430\u0442\u044c \u0431\u043e\u043b\u0435\u0435 \u0431\u044b\u0441\u0442\u0440\u043e, \u0435\u0441\u043b\u0438 \u0440\u0430\u0437\u0431\u0438\u0442\u044c \u0438\u0445 \u0440\u044f\u0434 \u0431\u043e\u043b\u0435\u0435 \u043f\u0440\u043e\u0441\u0442\u044b\u0445 \u0437\u0430\u0434\u0430\u0447 \u043f\u0443\u0442\u0451\u043c \u0432\u0432\u043e\u0434\u0430 \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0445 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0439.<\/p>\n
\u0421\u043f\u0430\u0441\u0438\u0431\u043e \u0437\u0430 \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u0435!<\/p>\n
\n\u041f\u043e\u043b\u043d\u044b\u0439 \u043a\u043e\u0434<\/summary>\n
\n
import pulp as pl import random as rnd from datetime import datetime # ========================================================================== def ssp(src: list, val: int):     \"\"\"     \u0417\u0430\u0434\u0430\u0447\u0430 \u043e \u0441\u0443\u043c\u043c\u0435 \u043f\u043e\u0434\u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432 \u043d\u0430\u0442\u0443\u0440\u0430\u043b\u044c\u043d\u044b\u0445 \u0447\u0438\u0441\u0435\u043b (Subset sum problem - SSP)     \"\"\"     n = len(src)     # \u041e\u0431\u044a\u044f\u0432\u043b\u044f\u0435\u043c \u043c\u043e\u0434\u0435\u043b\u044c     model = pl.LpProblem(name=\"ssp\", sense=pl.LpMinimize)            # \u041f\u043e\u0434\u043a\u043b\u044e\u0447\u0430\u0435\u043c \u0440\u0435\u0448\u0430\u0442\u0435\u043b\u044c CBC     solver = pl.PULP_CBC_CMD(msg=True)     # \u041e\u0431\u044a\u044f\u0432\u043b\u044f\u0435\u043c \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0435     x = [pl.LpVariable(name=f'x{i:05}', cat='Binary') for i in range(n)]         # \u0426\u0435\u043b\u0435\u0432\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f     model += pl.lpSum([x[i] for i in range(n)])         # \u041e\u0441\u043d\u043e\u0432\u043d\u043e\u0435 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435     model += pl.lpSum([x[i] * src[i] for i in range(n)]) == val         # \u041d\u0430\u0445\u043e\u0434\u0438\u043c \u0440\u0435\u0448\u0435\u043d\u0438\u0435     status = model.solve(solver)     if status == 1:         s = []         for j, v in enumerate(model.variables()):             if round(v.value()) > 0:                 s.append(src[j])         return s     return [] # ========================================================================== def ssp_optimized(src: list, val: int):     \"\"\"     \u0417\u0430\u0434\u0430\u0447\u0430 \u043e \u0441\u0443\u043c\u043c\u0435 \u043f\u043e\u0434\u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432 \u043d\u0430\u0442\u0443\u0440\u0430\u043b\u044c\u043d\u044b\u0445 \u0447\u0438\u0441\u0435\u043b \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c     (Subset sum problem optimized - SSP)     \"\"\"     n = len(src)     # \u041e\u0431\u044a\u044f\u0432\u043b\u044f\u0435\u043c \u043c\u043e\u0434\u0435\u043b\u044c     model = pl.LpProblem(name=\"ssp\", sense=pl.LpMinimize)         # \u041f\u043e\u0434\u043a\u043b\u044e\u0447\u0430\u0435\u043c \u0440\u0435\u0448\u0430\u0442\u0435\u043b\u044c CBC     solver = pl.PULP_CBC_CMD(msg=True)     # \u041e\u0431\u044a\u044f\u0432\u043b\u044f\u0435\u043c \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0435     x = [pl.LpVariable(name=f'x{i:05}', cat='Binary') for i in range(n)]     # \u0426\u0435\u043b\u0435\u0432\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f     model += pl.lpSum([x[i] for i in range(n)])     # \u041e\u0441\u043d\u043e\u0432\u043d\u043e\u0435 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435     model += pl.lpSum([x[i] * src[i] for i in range(n)]) == val      loop = list(range(1, n + 1))     loop = [loop.pop(0) if i % 2 == 0 else loop.pop(-1) for i in range(n)]     for val in loop:         # \u0423\u0441\u0442\u0430\u043d\u0430\u0432\u043b\u0438\u0432\u0430\u0435\u043c \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0435 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435 \u0448\u0430\u0433\u0430 \u0446\u0438\u043a\u043b\u0430         model.constraints['Y'] = pl.lpSum([x[j] for j in range(n)]) == val           # \u041d\u0430\u0445\u043e\u0434\u0438\u043c \u0440\u0435\u0448\u0435\u043d\u0438\u0435         status = model.solve(solver)           if status == 1:             s = []             for j, v in enumerate(model.variables()):                 if round(v.value()) > 0:                     s.append(src[j])             return s     return [] # ========================================================================== n = 23 rnd.seed(0) # \u0413\u0435\u043d\u0435\u0440\u0438\u0440\u0443\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u044b\u0439 \u0440\u044f\u0434 \u0447\u0438\u0441\u0435\u043b src = [rnd.randint(1000000, 2000000) for i in range(n)] t = sum(src) \/\/ 2 print(f'source = {src}') print()  start_time = datetime.now() res = ssp(src, t) date_diff = (datetime.now() - start_time).total_seconds() print('solution =', res) print('time =', date_diff) print()  start_time = datetime.now() res = ssp_optimized(src, t) date_diff = (datetime.now() - start_time).total_seconds() print('solution optimized =', res) print('time =', date_diff)<\/code><\/pre>\n<\/p>\n<\/div>\n<\/details>\n<\/div>\n<\/div>\n<\/div>\n
<\/div>\n

 \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438  https:\/\/habr.com\/ru\/articles\/806715\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"
<\/div>\n
\n
\n
\n
\n
<\/figure>\n
\u0417\u0430\u0434\u0430\u0447\u0430 \u043e \u0441\u0443\u043c\u043c\u0435 \u043f\u043e\u0434\u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432<\/a> \u0432 \u043e\u0431\u0449\u0435\u0439 \u0444\u043e\u0440\u043c\u0443\u043b\u0438\u0440\u043e\u0432\u043a\u0435 \u0437\u0432\u0443\u0447\u0438\u0442 \u0442\u0430\u043a: <\/p>\n
\u0421\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e S \u0447\u0438\u0441\u0435\u043b. \u0412\u043e\u043f\u0440\u043e\u0441 \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0432 \u0442\u043e\u043c, \u0431\u0443\u0434\u0435\u0442 \u043b\u0438 \u0441\u0443\u043c\u043c\u0430 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u043f\u043e\u0434\u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430 \u043e\u0442 S \u0440\u0430\u0432\u043d\u0430 \u0437\u0430\u0434\u0430\u043d\u043d\u043e\u043c\u0443 \u0447\u0438\u0441\u043b\u0443 \u0422.<\/em> <\/p>\n
\u0418\u0437\u0432\u0435\u0441\u0442\u043d\u043e, \u0447\u0442\u043e \u0434\u0430\u043d\u043d\u0430\u044f \u0437\u0430\u0434\u0430\u0447\u0430 NP-\u043f\u043e\u043b\u043d\u0430\u044f.<\/p>\n
\u041c\u044b \u0431\u0443\u0434\u0435\u043c \u0440\u0435\u0448\u0430\u0442\u044c \u044d\u043a\u0432\u0438\u0432\u0430\u043b\u0435\u043d\u0442\u043d\u0443\u044e \u0437\u0430\u0434\u0430\u0447\u0443, \u0433\u0434\u0435 \u0432\u0441\u0435 \u0447\u0438\u0441\u043b\u0430 \u044f\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u043d\u0430\u0442\u0443\u0440\u0430\u043b\u044c\u043d\u044b\u043c\u0438.<\/p>\n
\u0427\u0430\u0441\u0442\u043d\u044b\u043c \u0441\u043b\u0443\u0447\u0430\u0435\u043c \u0437\u0430\u0434\u0430\u0447\u0438 \u043e \u0441\u0443\u043c\u043c\u0435 \u043f\u043e\u0434\u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0437\u0430\u0434\u0430\u0447\u0430 \u0440\u0430\u0437\u0431\u0438\u0435\u043d\u0438\u044f \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430 \u0447\u0438\u0441\u0435\u043b<\/a>:<\/p>\n
\u041c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u0447\u0438\u0441\u0435\u043b S \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0440\u0430\u0437\u0431\u0438\u0442\u044c \u043d\u0430 \u0434\u0432\u0430 \u043f\u043e\u0434\u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430 S1 \u0438 S2, \u0433\u0434\u0435 \u0441\u0443\u043c\u043c\u0430 S1 \u0440\u0430\u0432\u043d\u0430 \u0441\u0443\u043c\u043c\u0435 S2.<\/em> <\/p>\n
(\u041e\u0442 \u0437\u0430\u0434\u0430\u0447\u0438 \u043e \u0441\u0443\u043c\u043c\u0435 \u043f\u043e\u0434\u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432 \u0442\u0435\u043a\u0443\u0449\u0430\u044f \u043e\u0442\u043b\u0438\u0447\u0430\u0435\u0442\u0441\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u0442\u0435\u043c, \u0447\u0442\u043e T = Sum(S1) \/ 2 = Sum(S2) \/ 2<\/em>)<\/p>\n
\u0425\u043e\u0447\u0443 \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0438\u0442\u044c \u0432\u0430\u043c \u043f\u0440\u043e\u0441\u0442\u043e\u0439 \u0438 \u044d\u043b\u0435\u0433\u0430\u043d\u0442\u043d\u044b\u0439 \u0441\u043f\u043e\u0441\u043e\u0431 \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0431\u044b\u0441\u0442\u0440\u043e\u0433\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u043e\u0431\u0435\u0438\u0445 \u0437\u0430\u0434\u0430\u0447 \u043c\u0435\u0442\u043e\u0434\u043e\u043c \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u043e\u0433\u043e \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0433\u043e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f<\/a> (\u0426\u041b\u041f). \u041c\u044b \u043f\u043e\u043b\u0443\u0447\u0438\u043c \u043d\u0435 \u0442\u043e\u043b\u044c\u043a\u043e \u0442\u043e\u0447\u043d\u044b\u0439 \u043e\u0442\u0432\u0435\u0442 \u043d\u0430 \u0432\u043e\u043f\u0440\u043e\u0441, \u043d\u043e \u0438 \u043d\u0430\u0439\u0434\u0451\u043c \u0438\u0441\u043a\u043e\u043c\u043e\u0435 \u043f\u043e\u0434\u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e.<\/p>\n
\u0418 \u0442\u0430\u043a, \u0443 \u043d\u0430\u0441 \u0435\u0441\u0442\u044c \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e S<\/em> \u043d\u0430\u0442\u0443\u0440\u0430\u043b\u044c\u043d\u044b\u0445 \u0447\u0438\u0441\u0435\u043b:<\/p>\n
\u041d\u0430\u043c \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u043e\u0442\u0432\u0435\u0442\u0438\u0442\u044c \u043d\u0430 \u0432\u043e\u043f\u0440\u043e\u0441: \u0412\u043e\u0437\u043c\u043e\u0436\u043d\u043e \u043b\u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0434\u0430\u043d\u043d\u043e\u0433\u043e \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430 \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u0441\u0443\u043c\u043c\u0443 \u0440\u0430\u0432\u043d\u0443\u044e T<\/em>?<\/p>\n
\u0414\u043b\u044f \u043d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u044f \u043e\u0442\u0432\u0435\u0442\u0430 \u043d\u0443\u0436\u043d\u043e \u0440\u0435\u0448\u0438\u0442\u044c \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0435 \u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0435: <\/p>\n
\u0415\u0441\u043b\u0438 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0431\u0443\u0434\u0435\u0442 \u043d\u0430\u0439\u0434\u0435\u043d\u043e, \u0442\u043e \u043e\u0442\u0432\u0435\u0442 \u043d\u0430 \u0432\u043e\u043f\u0440\u043e\u0441 \u043f\u043e\u043b\u043e\u0436\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0439, \u0435\u0441\u043b\u0438 \u0436\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u043d\u0435\u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e, \u0442\u043e \u043e\u0442\u0440\u0438\u0446\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0439. \u0415\u0441\u043b\u0438 \u0440\u0435\u0448\u0435\u043d\u0438\u0439 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e, \u043d\u0430\u0441 \u0443\u0441\u0442\u0440\u043e\u0438\u0442 \u043b\u044e\u0431\u043e\u0435.<\/p>\n
\u0418\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f Python \u0438 \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0443 PuLP<\/a>, \u043f\u0440\u043e\u0438\u043b\u043b\u044e\u0441\u0442\u0440\u0438\u0440\u0443\u0435\u043c \u043d\u0430 \u043f\u0440\u0438\u043c\u0435\u0440\u0435.<\/p>\n
import pulp as pl src = [59, 63, 15, 43, 75, 72, 61, 48, 71, 55] n = len(src)  # \u0418\u0441\u043a\u043e\u043c\u043e\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 val = sum(src) \/\/ 2 # \u041e\u0431\u044a\u044f\u0432\u043b\u044f\u0435\u043c \u043c\u043e\u0434\u0435\u043b\u044c model = pl.LpProblem(name=\"Subset sum problem\", sense=pl.LpMinimize)        # \u041f\u043e\u0434\u043a\u043b\u044e\u0447\u0430\u0435\u043c \u0440\u0435\u0448\u0430\u0442\u0435\u043b\u044c CBC solver = pl.PULP_CBC_CMD(msg=True) # \u041e\u0431\u044a\u044f\u0432\u043b\u044f\u0435\u043c \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0435 x = [pl.LpVariable(name=f'x{i:05}', cat='Binary') for i in range(n)]     # \u0426\u0435\u043b\u0435\u0432\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f model += pl.lpSum([x[i] for i in range(n)])     # \u041e\u0441\u043d\u043e\u0432\u043d\u043e\u0435 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435 model += pl.lpSum([x[i] * src[i] for i in range(n)]) == val  print(model)<\/code><\/pre>\n
\u0412 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0435 \u043c\u044b \u043f\u043e\u043b\u0443\u0447\u0438\u043c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0443\u044e \u043c\u043e\u0434\u0435\u043b\u044c \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0433\u043e \u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f:<\/p>\n
Subset sum problem: MINIMIZE 1*x00000 + 1*x00001 + 1*x00002 + 1*x00003 + 1*x00004 + 1*x00005  + 1*x00006 + 1*x00007 + 1*x00008 + 1*x00009 + 0 SUBJECT TO _C1: 59 x00000 + 63 x00001 + 15 x00002 + 43 x00003 + 75 x00004 + 72 x00005  + 61 x00006 + 48 x00007 + 71 x00008 + 55 x00009 = 281 VARIABLES 0 <= x00000 <= 1 Integer 0 <= x00001 <= 1 Integer 0 <= x00002 <= 1 Integer 0 <= x00003 <= 1 Integer 0 <= x00004 <= 1 Integer 0 <= x00005 <= 1 Integer 0 <= x00006 <= 1 Integer 0 <= x00007 <= 1 Integer 0 <= x00008 <= 1 Integer 0 <= x00009 <= 1 Integer<\/code><\/pre>\n
\u0417\u0430\u043f\u0443\u0441\u043a\u0430\u0435\u043c \u0440\u0435\u0448\u0430\u0442\u0435\u043b\u044c \u0438 \u0432\u044b\u0432\u043e\u0434\u0438\u043c \u0440\u0435\u0448\u0435\u043d\u0438\u0435<\/p>\n
# \u041d\u0430\u0445\u043e\u0434\u0438\u043c \u0440\u0435\u0448\u0435\u043d\u0438\u0435 status = model.solve(solver) res = [] if status == 1:         for j, v in enumerate(model.variables()):         if v.value() > 0:             res.append(src[j]) print('\u0420\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442:', sum(res), res)  \u0420\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442: 281 [63, 75, 72, 71]<\/code><\/pre>\n
\u0427\u0442\u043e \u0438 \u0442\u0440\u0435\u0431\u043e\u0432\u0430\u043b\u043e\u0441\u044c \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c.<\/p>\n
\u041e\u0434\u043d\u0430\u043a\u043e, \u0447\u0435\u043c \u0431\u043e\u043b\u044c\u0448\u0435 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0435 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u0438 \u0447\u0435\u043c \u043a\u0440\u0443\u043f\u043d\u0435\u0435 \u0432\u0435\u043b\u0438\u0447\u0438\u043d\u044b \u0435\u0433\u043e \u0441\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u044e\u0449\u0438\u0435, \u0442\u0435\u043c \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u0435\u0435 \u0438\u0434\u0451\u0442 \u043f\u043e\u0438\u0441\u043a \u0440\u0435\u0448\u0435\u043d\u0438\u044f. <\/p>\n
\u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440 \u0434\u043b\u044f \u043f\u043e\u0438\u0441\u043a\u0430 \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0433\u043e \u0441\u043f\u0438\u0441\u043a\u0430 \u0438\u0437 24 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u043f\u043e\u0442\u0440\u0435\u0431\u043e\u0432\u0430\u043b\u043e\u0441\u044c \u043f\u043e\u0440\u044f\u0434\u043a\u0430 \u0434\u0432\u0430\u0434\u0446\u0430\u0442\u0438 \u0441\u0435\u043a\u0443\u043d\u0434.<\/p>\n
source = [1485498, 1643002, 1391445, 1280110, 1145269, 1195187, 1908655, 1709512,            1006747, 1354760, 1527205, 1486247, 1941933, 1634072, 1084740, 1350249,            1581194, 1981871, 1646604, 1734106, 1042882, 1763564, 1397430, 1177643]<\/code><\/pre>\n
\u0412\u043e\u0437\u043c\u043e\u0436\u043d\u043e \u043b\u0438 \u043a\u0430\u043a-\u0442\u043e \u0443\u0441\u043a\u043e\u0440\u0438\u0442\u044c \u043f\u0440\u043e\u0446\u0435\u0441\u0441 \u043d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u044f? <\/p>\n
\u0418\u043c\u0435\u043d\u043d\u043e \u043e\u0442\u0432\u0435\u0442 \u043d\u0430 \u044d\u0442\u043e\u0442 \u0432\u043e\u043f\u0440\u043e\u0441 \u0438 \u043f\u043e\u0431\u0443\u0434\u0438\u043b \u043c\u0435\u043d\u044f \u043d\u0430\u043f\u0438\u0441\u0430\u0442\u044c \u0434\u0430\u043d\u043d\u044b\u0439 \u043f\u043e\u0441\u0442. \u0422\u0430\u043a \u043a\u0430\u043a \u0437\u0430\u0434\u0430\u0447\u0430 \u0426\u041b\u041f \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f NP-\u0441\u043b\u043e\u0436\u043d\u043e\u0439, \u0442\u043e \u0441\u0447\u0438\u0442\u0430\u0435\u0442\u0441\u044f \u0447\u0442\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043d\u0430\u0445\u043e\u0434\u0438\u0442 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u044d\u043a\u0441\u043f\u043e\u043d\u0435\u043d\u0446\u0438\u0430\u043b\u044c\u043d\u044b\u043c \u043e\u0442 \u0447\u0438\u0441\u043b\u0430 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432.<\/p>\n
\u041f\u043e\u044d\u0442\u043e\u043c\u0443 \u043f\u0440\u0435\u0434\u043b\u0430\u0433\u0430\u044e «\u0435\u0441\u0442\u044c \u0441\u043b\u043e\u043d\u0430 \u043f\u043e \u043a\u0443\u0441\u043e\u0447\u043a\u0430\u043c» (\u0440\u0430\u0437\u0431\u0438\u0442\u044c \u0441\u043b\u043e\u0436\u043d\u0443\u044e \u0437\u0430\u0434\u0430\u0447\u0443 \u043d\u0430 \u0431\u043e\u043b\u0435\u0435 \u043f\u0440\u043e\u0441\u0442\u044b\u0435 \u0438 \u043c\u0435\u043d\u0435\u0435 \u043e\u0431\u044a\u0435\u043c\u043d\u044b\u0435 \u0447\u0430\u0441\u0442\u0438). <\/p>\n
\u041c\u044b \u0440\u0430\u0437\u0434\u0435\u043b\u0438\u043c \u0437\u0430\u0434\u0430\u0447\u0443 \u043d\u0430 \u0440\u044f\u0434 \u0437\u0430\u0434\u0430\u0447 \u043c\u0435\u043d\u044c\u0448\u0435\u0439 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u0438 \u0432\u0432\u0435\u0434\u0435\u043d\u0438\u0435\u043c \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0445 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0439 \u0432 \u043c\u043e\u0434\u0435\u043b\u044c, \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u043c \u0438\u0445 \u043f\u043e \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438. \u0410 \u0437\u0430\u0442\u0435\u043c \u0432\u044b\u0431\u0435\u0440\u0435\u043c \u043e\u0434\u043d\u043e \u0438\u0437 \u0434\u043e\u043f\u0443\u0441\u0442\u0438\u043c\u044b\u0445 \u0440\u0435\u0448\u0435\u043d\u0438\u0439, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u0438 \u0431\u0443\u0434\u0435\u0442 \u0441\u0447\u0438\u0442\u0430\u0442\u044c\u0441\u044f \u0438\u0441\u043a\u043e\u043c\u044b\u043c.<\/p>\n
\u0414\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0435 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435 \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0439 \u0438\u0437 \u043f\u043e\u0434\u0437\u0430\u0434\u0430\u0447 \u0431\u0443\u0434\u0435\u0442 \u0437\u0432\u0443\u0447\u0430\u0442\u044c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c: \u0414\u043b\u044f \u043d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u044f \u0438\u0441\u043a\u043e\u043c\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 T<\/em> \u043d\u0430\u043c \u043f\u043e\u043d\u0430\u0434\u043e\u0431\u044f\u0442\u0441\u044f \u0440\u043e\u0432\u043d\u043e Y<\/em> \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432. \u0414\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0439 \u0438\u0437 \u043f\u043e\u0434\u0437\u0430\u0434\u0430\u0447 \u043c\u044b \u0431\u0443\u0434\u0435\u043c \u0431\u0440\u0430\u0442\u044c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 Y<\/em> \u0438\u0437 \u0441\u043f\u0438\u0441\u043a\u0430.<\/p>\n
Y<\/em> = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24]<\/p>\n
\n
\u041c\u0435\u0442\u0430\u0444\u043e\u0440\u0430: \u0434\u043b\u044f \u0443\u043f\u043e\u0442\u0440\u0435\u0431\u043b\u0435\u043d\u0438\u044f \u0432 \u043f\u0438\u0449\u0443 \u0440\u0430\u0437\u0440\u0435\u0437\u0430\u043d\u043d\u044b\u0439 \u043d\u0430 \u043b\u043e\u043c\u0442\u0438\u043a\u0438 \u0431\u0430\u0442\u043e\u043d \u0441\u044a\u0435\u0441\u0442\u044c \u043f\u0440\u043e\u0449\u0435, \u0447\u0435\u043c \u0440\u0430\u0437\u0436\u0435\u0432\u0430\u0442\u044c \u0435\u0433\u043e \u0446\u0435\u043b\u0438\u043a\u043e\u043c.<\/figcaption><\/div>\n<\/figure>\n
\u041e\u0431\u0440\u0430\u0442\u0438\u0442\u0435 \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u0435, \u043a\u0430\u043a \u0438 \u0432 \u043c\u0435\u0442\u0430\u0444\u043e\u0440\u0435 \u0441 \u0431\u0430\u0442\u043e\u043d\u043e\u043c, \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u043f\u043e \u043a\u0440\u0430\u044f\u043c \u0431\u0443\u0434\u0443\u0442 \u043c\u0435\u043d\u044c\u0448\u0435\u0433\u043e \u0440\u0430\u0437\u043c\u0435\u0440\u0430, \u043f\u043e\u0442\u043e\u043c\u0443 \u043d\u0430\u0445\u043e\u0434\u044f\u0442\u0441\u044f \u0431\u044b\u0441\u0442\u0440\u0435\u0435. \u041f\u0440\u0435\u0434\u043b\u0430\u0433\u0430\u044e \u043d\u0430\u0447\u0438\u043d\u0430\u0442\u044c \u0438\u043c\u0435\u043d\u043d\u043e \u0441 \u043a\u0440\u0430\u0451\u0432, \u0442\u0430\u043a \u043a\u0430\u043a \u043d\u0430\u0439\u0434\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u043c\u043e\u0436\u043d\u043e \u043e\u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u044c \u043f\u043e\u0438\u0441\u043a \u043e\u0441\u0442\u0430\u043b\u044c\u043d\u044b\u0445 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0445 \u0440\u0435\u0448\u0435\u043d\u0438\u0439, \u044d\u043a\u043e\u043d\u043e\u043c\u044f \u0432\u0440\u0435\u043c\u044f.<\/p>\n
Y<\/em> = [1, 24, 2, 23, 3, 22, 4, 21, 5, 20, 6, 19, 7, 18, 8, 17, 9, 16, 10, 15, 11, 14, 12, 13]<\/p>\n
\u0427\u0438\u0442\u0430\u0442\u044c \u043d\u0443\u0436\u043d\u043e \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c: \u0421\u0443\u043c\u043c\u0430 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 \u043b\u044e\u0431\u044b\u0445 Y<\/em> \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430 \u0434\u043e\u043b\u0436\u043d\u0430 \u0431\u044b\u0442\u044c \u0440\u0430\u0432\u043d\u0430 \u0438\u0441\u043a\u043e\u043c\u043e\u043c\u0443 T<\/em>, \u0433\u0434\u0435 Y<\/em> \u2013 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0438\u0437 \u0441\u043f\u0438\u0441\u043a\u0430 \u0432\u044b\u0448\u0435.<\/p>\n
\u0420\u0435\u0448\u0430\u044f \u043f\u043e\u0434\u0437\u0430\u0434\u0430\u0447\u0438 \u043f\u043e \u0442\u0430\u043a\u043e\u0439 \u0441\u0445\u0435\u043c\u0435, \u043c\u044b \u043d\u0430\u0439\u0434\u0451\u043c \u043e\u0442\u0432\u0435\u0442 \u0431\u044b\u0441\u0442\u0440\u0435\u0435, \u0447\u0435\u043c \u0440\u0435\u0448\u0430\u044f \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b\u044c\u043d\u0443\u044e \u0437\u0430\u0434\u0430\u0447\u0443. \u0422\u0430\u043a \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440 \u0434\u043b\u044f \u043d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0434\u043b\u044f \u0440\u044f\u0434\u0430 \u0432\u044b\u0448\u0435, \u043f\u043e\u043d\u0430\u0434\u043e\u0431\u0438\u0442\u0441\u044f \u043d\u0435\u043c\u043d\u043e\u0433\u0438\u043c \u0431\u043e\u043b\u0435\u0435 \u0434\u0432\u0443\u0445 \u0441\u0435\u043a\u0443\u043d\u0434.<\/p>\n
\u041e\u0442\u043b\u0438\u0447\u0438\u0435 \u043e\u0442 \u043a\u043e\u0434\u0430 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0435\u0433\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0431\u0443\u0434\u0435\u0442 \u0442\u043e\u043b\u044c\u043a\u043e \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u043c\u044b \u0431\u0443\u0434\u0435\u043c \u0438\u0441\u043a\u0430\u0442\u044c \u043d\u0435 \u043e\u0434\u043d\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u0435, \u0430 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e:<\/p>\n
loop = list(range(1, n + 1)) loop = [loop.pop(0) if i % 2 == 0 else loop.pop(-1) for i in range(n)] for val in loop:     # \u0423\u0441\u0442\u0430\u043d\u0430\u0432\u043b\u0438\u0432\u0430\u0435\u043c \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0435 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435 \u0448\u0430\u0433\u0430 \u0446\u0438\u043a\u043b\u0430     model.constraints['Y'] = pl.lpSum([x[j] for j in range(n)]) == val      print(model)          # \u041d\u0430\u0445\u043e\u0434\u0438\u043c \u0440\u0435\u0448\u0435\u043d\u0438\u0435     status = model.solve(solver)       if status == 1:         res = []         for j, v in enumerate(model.variables()):             if v.value() > 0:                 res.append(src[j])             return res return []<\/code><\/pre>\n
\u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c \u043c\u044b \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e \u0431\u0443\u0434\u0435\u043c \u0441\u0442\u0440\u043e\u0438\u0442\u044c \u0440\u044f\u0434 \u043c\u043e\u0434\u0435\u043b\u0435\u0439 \u0438 \u043f\u044b\u0442\u0430\u0442\u044c\u0441\u044f \u043d\u0430\u0439\u0442\u0438 \u0440\u0435\u0448\u0435\u043d\u0438\u0435.<\/p>\n
Subset sum problem: MINIMIZE 1*x00000 + 1*x00001 + 1*x00002 + 1*x00003 + 1*x00004 + 1*x00005 + 1*x00006  + 1*x00007 + 1*x00008 + 1*x00009 + 1*x00010 + 1*x00011 + 1*x00012 + 1*x00013  + 1*x00014 + 1*x00015 + 1*x00016 + 1*x00017 + 1*x00018 + 1*x00019 + 1*x00020  + 1*x00021 + 1*x00022 + 1*x00023 + 0 SUBJECT TO _C1: 1485498 x00000 + 1643002 x00001 + 1391445 x00002 + 1280110 x00003  + 1145269 x00004 + 1195187 x00005 + 1908655 x00006 + 1709512 x00007  + 1006747 x00008 + 1354760 x00009 + 1527205 x00010 + 1486247 x00011  + 1941933 x00012 + 1634072 x00013 + 1084740 x00014 + 1350249 x00015  + 1581194 x00016 + 1981871 x00017 + 1646604 x00018 + 1734106 x00019  + 1042882 x00020 + 1763564 x00021 + 1397430 x00022 + 1177643 x00023  = 17734962  Y: x00000 + x00001 + x00002 + x00003 + x00004 + x00005 + x00006 + x00007  + x00008 + x00009 + x00010 + x00011 + x00012 + x00013 + x00014 + x00015  + x00016 + x00017 + x00018 + x00019 + x00020 + x00021 + x00022 + x00023 = 1  VARIABLES 0 <= x00000 <= 1 Integer 0 <= x00001 <= 1 Integer 0 <= x00002 <= 1 Integer 0 <= x00003 <= 1 Integer 0 <= x00004 <= 1 Integer 0 <= x00005 <= 1 Integer 0 <= x00006 <= 1 Integer 0 <= x00007 <= 1 Integer 0 <= x00008 <= 1 Integer 0 <= x00009 <= 1 Integer 0 <= x00010 <= 1 Integer 0 <= x00011 <= 1 Integer 0 <= x00012 <= 1 Integer 0 <= x00013 <= 1 Integer 0 <= x00014 <= 1 Integer 0 <= x00015 <= 1 Integer 0 <= x00016 <= 1 Integer 0 <= x00017 <= 1 Integer 0 <= x00018 <= 1 Integer 0 <= x00019 <= 1 Integer 0 <= x00020 <= 1 Integer 0 <= x00021 <= 1 Integer 0 <= x00022 <= 1 Integer 0 <= x00023 <= 1 Integer<\/code><\/pre>\n
\u041e\u0442\u043b\u0438\u0447\u0430\u0442\u044c\u0441\u044f \u043e\u043d\u0438 \u0431\u0443\u0434\u0443\u0442 \u0442\u043e\u043b\u044c\u043a\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435\u043c \u043f\u0440\u0430\u0432\u043e\u0439 \u0447\u0430\u0441\u0442\u0438 \u0440\u0430\u0432\u0435\u043d\u0441\u0442\u0432\u0430 \u0432 18 \u0441\u0442\u0440\u043e\u043a\u0435.<\/p>\n
\u041f\u043e\u0434\u0445\u043e\u0434 \u043e\u043f\u0438\u0441\u0430\u043d\u043d\u044b\u0439 \u0432 \u0440\u0430\u0431\u043e\u0442\u0435 \u0445\u043e\u0442\u044c \u0438 \u043d\u0435 \u0438\u0434\u0435\u0430\u043b\u044c\u043d\u044b\u0439, \u043d\u043e \u0432\u043f\u043e\u043b\u043d\u0435 \u0440\u0430\u0431\u043e\u0447\u0438\u0439. \u041d\u0435\u0441\u043c\u043e\u0442\u0440\u044f \u043d\u0430 \u0442\u043e, \u0447\u0442\u043e \u0441\u0430\u043c\u0430 \u0437\u0430\u0434\u0430\u0447\u0430 NP-\u0441\u043b\u043e\u0436\u043d\u0430, \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u044c \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0434\u043b\u044f \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432 \u043e\u0442 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u0438\u0445 \u0434\u0435\u0441\u044f\u0442\u043a\u043e\u0432 \u0434\u043e \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u0438\u0445 \u0441\u043e\u0442\u0435\u043d \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0432 \u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u0438 \u043e\u0442 \u0438\u0441\u0445\u043e\u0434\u043d\u044b\u0445 \u0434\u0430\u043d\u043d\u044b\u0445.<\/p>\n
\n\u041f\u0440\u0438\u043c\u0435\u0447\u0430\u043d\u0438\u0435<\/summary>\n
\n
\u041e\u0442\u0434\u0435\u043b\u044c\u043d\u043e \u0441\u0442\u043e\u0438\u0442 \u043e\u0442\u043c\u0435\u0442\u0438\u0442\u044c, \u0447\u0442\u043e \u043d\u0435 \u043a\u0430\u0436\u0434\u044b\u0439 \u0440\u0435\u0448\u0430\u0442\u0435\u043b\u044c \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u0445 \u043b\u0438\u043d\u0435\u0439\u043d\u044b\u0445 \u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0439 \u0441\u043f\u043e\u0441\u043e\u0431\u0435\u043d \u0442\u043e\u0447\u043d\u043e \u0440\u0435\u0448\u0438\u0442\u044c \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u0443\u044e \u043b\u0438\u043d\u0435\u0439\u043d\u0443\u044e \u0437\u0430\u0434\u0430\u0447\u0443. \u0418\u0437-\u0437\u0430 \u043e\u0441\u043e\u0431\u0435\u043d\u043d\u043e\u0441\u0442\u0435\u0439 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u043c\u043d\u043e\u0433\u0438\u0435 \u0440\u0435\u0448\u0430\u0442\u0435\u043b\u0438 \u043f\u0440\u0438\u0441\u0443\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0435 \u043d\u0430 \u0440\u044b\u043d\u043a\u0435 \u0438\u043c\u0435\u044e\u0442 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u0443\u044e \u043f\u043e\u0433\u0440\u0435\u0448\u043d\u043e\u0441\u0442\u044c \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0439, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043d\u0435\u0437\u043d\u0430\u0447\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0432\u043b\u0438\u044f\u0435\u0442 \u043d\u0430 \u043a\u043e\u043d\u0435\u0447\u043d\u044b\u0439 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u0432 \u0442\u0438\u043f\u043e\u0432\u044b\u0445 \u0437\u0430\u0434\u0430\u0447\u0430\u0445. \u041d\u043e \u0432 \u0434\u0430\u043d\u043d\u043e\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0435, \u0440\u0430\u0437 \u0443\u0436 \u043c\u044b \u0433\u043e\u0432\u043e\u0440\u0438\u043c \u043f\u0440\u043e \u0442\u043e\u0447\u043d\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435<\/strong>, \u043e\u0441\u043e\u0431\u0435\u043d\u043d\u043e \u043f\u0440\u0438 \u0431\u043e\u043b\u044c\u0448\u0438\u0445 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f\u0445 \u0432\u0445\u043e\u0434\u043d\u044b\u0445 \u0434\u0430\u043d\u043d\u044b\u0445, \u0432\u044b\u0431\u043e\u0440 \u0440\u0435\u0448\u0430\u0442\u0435\u043b\u044f \u043c\u043e\u0436\u0435\u0442 \u043a\u0430\u0442\u0430\u0441\u0442\u0440\u043e\u0444\u0438\u0447\u0435\u0441\u043a\u0438 \u043f\u043e\u0432\u043b\u0438\u044f\u0442\u044c \u043d\u0430 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442.<\/p>\n
\u0412 \u043c\u043e\u0438\u0445 \u0442\u0435\u0441\u0442\u0430\u0445 \u0442\u043e\u043b\u044c\u043a\u043e CBC <\/a>\u043e\u0442 COIN-OR Foundation \u0438 OR-Tools<\/a> \u043e\u0442 Google, \u0441\u043f\u0440\u0430\u0432\u0438\u043b\u0438\u0441\u044c \u0441 \u0434\u0430\u043d\u043d\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0435\u0439 \u0432\u0435\u0440\u043d\u043e.<\/p>\n<\/div>\n<\/details>\n
\u0417\u0430\u043a\u043b\u044e\u0447\u0435\u043d\u0438\u0435: <\/p>\n
\u041d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0437\u0430\u0434\u0430\u0447\u0438 \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u043e\u0433\u043e \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0433\u043e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u043c\u043e\u0436\u043d\u043e \u0440\u0435\u0448\u0430\u0442\u044c \u0431\u043e\u043b\u0435\u0435 \u0431\u044b\u0441\u0442\u0440\u043e, \u0435\u0441\u043b\u0438 \u0440\u0430\u0437\u0431\u0438\u0442\u044c \u0438\u0445 \u0440\u044f\u0434 \u0431\u043e\u043b\u0435\u0435 \u043f\u0440\u043e\u0441\u0442\u044b\u0445 \u0437\u0430\u0434\u0430\u0447 \u043f\u0443\u0442\u0451\u043c \u0432\u0432\u043e\u0434\u0430 \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0445 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0439.<\/p>\n
\u0421\u043f\u0430\u0441\u0438\u0431\u043e \u0437\u0430 \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u0435!<\/p>\n
\n\u041f\u043e\u043b\u043d\u044b\u0439 \u043a\u043e\u0434<\/summary>\n
\n
import pulp as pl import random as rnd from datetime import datetime # ========================================================================== def ssp(src: list, val: int):     \"\"\"     \u0417\u0430\u0434\u0430\u0447\u0430 \u043e \u0441\u0443\u043c\u043c\u0435 \u043f\u043e\u0434\u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432 \u043d\u0430\u0442\u0443\u0440\u0430\u043b\u044c\u043d\u044b\u0445 \u0447\u0438\u0441\u0435\u043b (Subset sum problem - SSP)     \"\"\"     n = len(src)     # \u041e\u0431\u044a\u044f\u0432\u043b\u044f\u0435\u043c \u043c\u043e\u0434\u0435\u043b\u044c     model = pl.LpProblem(name=\"ssp\", sense=pl.LpMinimize)            # \u041f\u043e\u0434\u043a\u043b\u044e\u0447\u0430\u0435\u043c \u0440\u0435\u0448\u0430\u0442\u0435\u043b\u044c CBC     solver = pl.PULP_CBC_CMD(msg=True)     # \u041e\u0431\u044a\u044f\u0432\u043b\u044f\u0435\u043c \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0435     x = [pl.LpVariable(name=f'x{i:05}', cat='Binary') for i in range(n)]         # \u0426\u0435\u043b\u0435\u0432\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f     model += pl.lpSum([x[i] for i in range(n)])         # \u041e\u0441\u043d\u043e\u0432\u043d\u043e\u0435 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435     model += pl.lpSum([x[i] * src[i] for i in range(n)]) == val         # \u041d\u0430\u0445\u043e\u0434\u0438\u043c \u0440\u0435\u0448\u0435\u043d\u0438\u0435     status = model.solve(solver)     if status == 1:         s = []         for j, v in enumerate(model.variables()):             if round(v.value()) > 0:                 s.append(src[j])         return s     return [] # ========================================================================== def ssp_optimized(src: list, val: int):     \"\"\"     \u0417\u0430\u0434\u0430\u0447\u0430 \u043e \u0441\u0443\u043c\u043c\u0435 \u043f\u043e\u0434\u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432 \u043d\u0430\u0442\u0443\u0440\u0430\u043b\u044c\u043d\u044b\u0445 \u0447\u0438\u0441\u0435\u043b \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c     (Subset sum problem optimized - SSP)     \"\"\"     n = len(src)     # \u041e\u0431\u044a\u044f\u0432\u043b\u044f\u0435\u043c \u043c\u043e\u0434\u0435\u043b\u044c     model = pl.LpProblem(name=\"ssp\", sense=pl.LpMinimize)         # \u041f\u043e\u0434\u043a\u043b\u044e\u0447\u0430\u0435\u043c \u0440\u0435\u0448\u0430\u0442\u0435\u043b\u044c CBC     solver = pl.PULP_CBC_CMD(msg=True)     # \u041e\u0431\u044a\u044f\u0432\u043b\u044f\u0435\u043c \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0435     x = [pl.LpVariable(name=f'x{i:05}', cat='Binary') for i in range(n)]     # \u0426\u0435\u043b\u0435\u0432\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f     model += pl.lpSum([x[i] for i in range(n)])     # \u041e\u0441\u043d\u043e\u0432\u043d\u043e\u0435 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435     <\/code><\/pre>\n<\/div>\n<\/details>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-373245","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/373245","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=373245"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/373245\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=373245"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=373245"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=373245"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}