algorithm - 这个问题可以使用背包问题解决方法来解决吗(不同大小的背包？)

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 将是 value，NonVerif 将是 Weight，以查看提供最佳比率的项目来选择这些项目)；示例中的列表按 Div 降序排序。天真的方法是选择按顺序清理哪些账户，直到银行遵守规定。

我正在考虑使用 Avikalp Srivastava 建议的方法 here :因此 Verif (value) 将被视为权重，NonVerif (cost) 将被视为值(value)；然后将使用常规的背包问题解决方法来找到在 Verif 保持 >= 90% *(银行持有的总资金)的情况下可以去除的最大成本；问题是，当您将不干净的元素添加到背包中时，银行持有的总资金会减少，因为银行会将这笔钱退还给客户(因此，随着更多元素被添加到背包中，背包会变小吗？)。蛮力导致显示的数据内存溢出。实际上，我花了好几个小时试图解决这个问题，却没有接近答案。也许背包问题解决不是这个(？)的正确方法

天真的方法足以满足我的目的，但我仍然想找出如何正确解决它。

Answer 1

注意:此方法基于我在上述评论中的理解。如果我的理解有误，我会进行编辑。

这是一种基于整数线性规划 (ILP) 的方法。

• 令I 为所有帐户的集合，让I_c 和I_n 分别为干净帐户和非干净帐户的集合。
• 设V[i] 和NV[i] 为帐户i 的可验证和不可验证资金数额。
• 令 r 为必须干净的资金比例(例如 90%)。

(这些是参数——模型的输入。)

• 让 x[i] = 1 如果我们清理帐户 i，对于 I_n 中的 i，并且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_n 中的每个 i，如果我们清理账户，那么我们就可以去掉 NV[i] 金额。)第一个约束表示总干净钱必须至少是总钱的 0.9:总干净钱是原始干净钱 (sum {i in I_c} V[i]) 加上新清理的钱(求和 {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，或任意数量的其他线性规划包。