这个问题可以使用背包问题解决方法来解决吗（不同大小的背包？）

Question

为了遵守法规，银行需要确保其持有的资金中至少有 90%（或其他固定比例）是“干净的”。

如果钱在一个“干净”的账户里，就被认为是干净的。如果账户中的所有资金都来自可验证的来源，则该账户被认为是“干净的”。

银行可以强行return从无法验证的来源向客户提供资金，以增加"clean"资金的比例以符合规定。问题是确定银行需要 return 遵守规定的最低金额。

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 将是权重，以查看与 select 那些提供最佳比率的项目） ;示例中的列表按 Div 降序排序。天真的方法是选择按顺序清理哪些账户，直到银行遵守规定。

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

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

Answer 1

一个想法可能是对目标 non-verified 进行二分搜索，总计 return。然后对于每个这样的候选人，运行一个背包，其中该候选人是最大重量，每个 non-verified 数量是重量，而要最大化的值是账户中的可验证数量。（当然，我们只需要查询有non-verified个资金的账户即可。）

Answer 2

注意：此方法是基于我在上面评论中的理解。如果我的理解有误，我会编辑。

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

设 I 为所有帐户的集合，并让 I_c 和 I_n 分别为干净帐户和 non-clean 帐户的集合。
设 V[i] 和 NV[i] 为帐户 i 的可验证金额和 non-verifiable 资金。
设 r 为必须干净的资金比例（例如 90%）。

（这些是参数——模型的输入。）

如果我们清理帐户 i，则让 x[i] = 1，对于 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

objective 函数最小化清理的总资金。（对于 I_n 中的每个 i，如果我们清理账户，那么我们会去掉 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，或任意数量的其他线性规划包。

这个问题可以使用背包问题解决方法来解决吗（不同大小的背包？）

Can this problem be solved using knapsack problem-solving approach (varying-size knapsack?)

algorithm

optimization

knapsack-problem

dynamic-programming