Может ли эта проблема быть решена с помощью подхода к решению проблем с ранцем (рюкзак различного размера?)

Question

Для соблюдения нормативных требований банк должен убедиться, что по крайней мере 90% (или некоторая другая фиксированная пропорция) денег, которые он имеет, являются «чистыми».

Деньги считаются чистыми, если они находятся на «чистом» счете. Счет считается «чистым», если все деньги в нем поступают из проверяемого источника.

Банк может принудительно вернуть деньги клиентам, поступившим из неподтвержденного источника, чтобы увеличить долю «чистых» денег в соответствии с правилами. Задача состоит в том, чтобы определить минимальную сумму, которую необходимо вернуть банку для соблюдения правил.

Account Verif   NonVerif    Divi    Clean   NotClean
1   889.77  157.01  5.67    0   1046.78
2   907.88  160.21  5.67    0   1068.09
3   1187.18 209.5   5.67    0   1396.68
4   918.12  162.02  5.67    0   1080.14
5   1721.88 303.86  5.67    0   2025.74
6   828.17  276.05  3.00    0   1104.22
7   1127.6  375.86  3.00    0   1503.46
8   1177.13 392.37  3.00    0   1569.5
9   801.81  267.27  3.00    0   1069.08
10  741.9   247.3   3.00    0   989.2
11  0   1468.11 0.00    0   1468.11
12  0   853.66  0.00    0   853.66
13  2354.81 0   -1.00   2354.81 0
14  2267.1  0   -1.00   2267.1  0
15  2238.3  0   -1.00   2238.3  0
16  2188.66 0   -1.00   2188.66 0
17  2167.85 0   -1.00   2167.85 0
18  2166.1  0   -1.00   2166.1  0
19  2165.59 0   -1.00   2165.59 0
20  2163.84 0   -1.00   2163.84 0
21  2145.43 0   -1.00   2145.43 0
22  2117.76 0   -1.00   2117.76 0
23  1320.26 0   -1.00   1320.26 0
24  1299.99 0   -1.00   1299.99 0
25  1241.02 0   -1.00   1241.02 0
26  1237.36 0   -1.00   1237.36 0
27  1208.74 0   -1.00   1208.74 0
28  1114.58 0   -1.00   1114.58 0
29  1048.63 0   -1.00   1048.63 0
30  1010.92 0   -1.00   1010.92 0
31  971.1   0   -1.00   971.1   0
32  874.95  0   -1.00   874.95  0
33  832.01  0   -1.00   832.01  0
34  825.72  0   -1.00   825.72  0
TOTAL   45262.16    4873.22     34960.72    15174.66

В приведенном выше примере общая сумма денег, находящихся в банке, составляет 34960,72 + 15174,66 = 50135,38; без какой-либо очистки, только 69,7% (34960,72 / 50135,38 = 0,697 ...) могут считаться чистыми, поэтому банку необходимо провести очистку, чтобы соответствовать требованиям.

Если бы банк очистил первые два счета, то общая сумма денег в банке составила бы 50135,38 - 157,01 - 160,21 = 49818,16, а чистые деньги - 34960,72 + 889,77 + 907,88 = 36758,37; доля чистых денег будет 36758,37 / 49818,16 = 73,7%.

В приведенном выше примере Div = Verif / NonVerif (Verif будет значением, а NonVerif будет весом, чтобы увидеть элементы, обеспечивающие наилучшее соотношение для их выбора); список в примере отсортирован по убыванию Div. Наивный подход состоит в том, чтобы выбрать, какие счета следует очищать в этом порядке до тех пор, пока банк не соблюдает правила.

Я думал об использовании подхода, предложенного Авикальпом Шриваставой здесь : поэтому Verif (значение) будет рассматриваться как вес, а NonVerif (стоимость) будет рассматриваться как значение; тогда для решения максимальной стоимости, которая может быть удалена, будет использоваться подход к решению обычных задач по ранцу, если Verif остается> = 90% * (общая сумма денег, удерживаемая банком); Дело в том, что общая сумма денег в банке уменьшается, когда вы добавляете неочищенные вещи в рюкзак, потому что банк возвращает эти деньги клиенту (так что рюкзак будет уменьшаться по мере добавления к нему большего количества предметов?). Грубая сила вызвала переполнение памяти для указанных данных Я часами пытался решить эту проблему, не приближаясь к ответу. Может быть, решение проблем с рюкзаком не является правильным подходом для этого (?)

Наивного подхода будет достаточно для моих целей, но я все еще хочу выяснить, как правильно его решить.

Answer 1

Примечание: этот подход основан на моем понимании в комментарии выше. Если мое понимание неверно, я отредактирую.

Вот подход, основанный на целочисленном линейном программировании (ILP).

• Пусть I будет набором всех учетных записей, а I_c и I_n - набором чистых и не чистых учетных записей соответственно.
• Пусть V[i] и NV[i] будут суммами поддающихся проверке и не поддающихся проверке средств для счета i.
• Пусть r будет доля средств, которые должны быть чистыми (например, 90%).

(Это параметры - входные данные для модели.)

• Пусть x[i] = 1, если мы очистим аккаунт i, для i в I_n и 0 в противном случае. (Мы не будем чистить аккаунты в I_c.)

(Это двоичная переменная принятия решения - переменная, для которой модель установит значение.)

Тогда ILP будет:

minimize sum {i in I_n} NV[i] * x[i]
subject to sum {i in I_c} V[i] + sum {i in I_n} V[i] * x[i] >= 
               r * (sum {i in I} (NV[i] + V[i]) - sum {i in I_n} NV[i] * x[i]))
           x[i] in {0,1} for all i in I_n

Целевая функция минимизирует общее количество очищенных средств. (Для каждого i в I_n, если мы очищаем счет, мы избавляемся от NV[i] суммы денег.) Первое ограничение говорит, что чистые деньги должны составлять не менее 0,9 от общей суммы денег: чистые деньги - это чистые деньги (sum {i in I_c} V[i]) плюс чистые деньги (sum {i in I_n} V[i] * x[i]); и общая сумма денег равна первоначальной сумме (подтверждено плюс не подтверждено) за вычетом очищенных средств. Второе ограничение просто говорит, что все переменные x[i] должны быть двоичными.

С точки зрения реализации, вы, безусловно, можете решить эту проблему в Excel / Solver. (Я подозреваю, что нелинейность вы получили, потому что вы писали ограничение больше похоже на

sum {i in I_c} V[i] + sum {i in I_n} V[i] * x[i] / (sum {i in I} (NV[i] + V[i]) - sum {i in I_n} NV[i] * x[i])) >= r

, что является нелинейным.) Вы также можете использовать Python / PuLP или любое количество других пакетов линейного программирования.

Answer 2

Одной из идей может быть бинарный поиск по целевому непроверенному количеству для возврата. Затем для каждого такого кандидата запустите рюкзак, где этот кандидат является максимальным весом, каждая непроверенная сумма является весом, а значение для максимизации - это проверяемые суммы в счетах. (Конечно, нам нужно запрашивать только те аккаунты, у которых есть неподтвержденные средства.)