如何找到符合指定分布的最优组合？大规模数据近似解法需求

我需要对DataFrame进行采样，让采样内容的总和符合特定分布。以装水果篮场景为例：每次只能添加预定义的水果组合，篮子对每种水果有容量上限，DataFrame内容可表示为如下矩阵：

比如篮子最多容纳3个苹果、3个香蕉、3个橙子时，选择组合1和组合2可刚好填满容量。但当前DataFrame包含数万种组合，采用贪心搜索耗时过长，想找允许少量误差的近似组合求解方法。

以下是几种实用的近似解法：

1. 分阶段启发式贪心 #

放弃纯贪心“每次选最优”的思路，改成分阶段筛选：

• 第一阶段：先过滤掉所有单种水果数量超过当前剩余容量的组合，计算每个组合与剩余容量的匹配度（比如用曼哈顿距离，数值越小越匹配），取匹配度最高的前200个组合，从中挑选能最大化消耗剩余容量且不溢出的组合。
• 第二阶段：当剩余容量小于所有组合的最小单种水果量时，切换为“补漏模式”，只选能填补剩余小容量的组合，避免选大组合导致浪费。

2. 随机采样+迭代调优 #

• 先随机抽取1000-5000组组合（数量根据计算资源调整），计算每组总水果量与目标容量的误差，保留误差最小的10%。
• 对保留的组合进行迭代调整：随机替换其中一个组合，若新组合的误差更小则保留，重复200-500次迭代，直到误差不再明显下降。
• 这种方法计算速度快，适合组合数量极多的场景，误差可控。

3. 松弛整数约束的线性规划近似 #

把问题转化为线性规划问题求解：

• 设每个组合的选择次数为x_i（原本是整数，先松弛为实数），目标是最小化总水果量与目标容量的误差平方和，约束是各组合水果量乘以x_i的总和不超过容量上限。
• 用scipy.optimize.linprog求解得到实数解后，将x_i四舍五入为整数，再微调（比如把小数部分大的x_i加1，小的减1），确保不超过容量上限。
• 这种方法误差小，适合有线性代数基础的场景。

4. 聚类降维后求解 #

• 先用K-Means对所有组合做聚类，把数万种组合聚成50-200类，每类选一个最具代表性的组合（比如类中心对应的组合）。
• 然后在这些代表组合里用贪心或线性规划求解，大幅减少计算量，误差来自聚类近似，只要聚类合理，误差可接受。

内容的提问来源于stack exchange，提问作者CapsLk