问题标签 [partition-problem]

所以不知何故，我的一个亲戚得到了这些餐厅代金券，可以用来从每张收据中扣除 500 泰铢。可以要求餐厅开出多张收据，以便可以使用多张代金券。亲戚希望尽可能少花钱（超过500的礼券价值必须以现金支付）

更正式地说，问题是：

given a list of prices (being the prices of items to be ordered), what are the combinations of prices that would require the least amount of cash to be paid?

例如：

让价格=[425, 105, 185, 185, 185, 98, 145, 155, 125, 125, 135, 295, 295, 155, 125]

如果我只是按给定顺序对价格求和，当总和超过 500 时停止：

[425 + 105], [185 + 185 + 185], [98 + 145 + 155 + 125], [125 + 135 + 295], [295 + 155 + 125]

每个组合的总和：

[530, 555, 523, 555, 575]

超过500的金额： [30, 55, 23, 55, 75]

支付现金总额：238

需要最少现金的最佳价格组合是什么？

到目前为止，我已经尝试了一种蛮力方法，通过生成价格的所有排列并以与上述示例相同的方式计算每个排列所需的现金金额（从左到右求和，当 >= 500 时停止）。但是，当价格超过 10 个时，这种方法会导致 heap out of memory 错误:(

提前致谢。

我正在使用 AWS Athena 查询 S3 存储桶，该存储桶仅按天分区数据，分区看起来像day=yyyy/mm/dd。当我尝试使用 Glue 每天运行更新分区时，它每天都会创建新表（同步 2017 年，大约 1500 个表）。

我尝试像这样使用分区投影：

但是没有 MSCK 修复，分区不会更新。有任何想法吗？我错过了分区投影的一些东西吗？

我正在尝试实现 Karmarkar-Karp 启发式数字分区算法的 k 分区版本。但我在第二阶段苦苦挣扎，从结果差异集重建数字分区。

我能找到的用一些伪代码彻底描述第二阶段的唯一来源是论文的第 58 页：通过多标准图分区实现多物理场仿真的负载平衡。

给定多重集 S = [1,7,5,10,9,3] 将其划分为三个 (k=3) 子集，该算法经历了 2 个阶段。

阶段1：

它首先按降序对 S 进行排序：

S = [10,9,7,5,3,1]

然后，将 S 中的每个数字转换为大小为 k 的元组，第一个条目是数字本身，其他条目为零：

M = [[10,0,0],[9,0,0],[7,0,0],[5,0,0],[3,0,0],[1,0,0] ]

这将创建矩阵 M。

在每一步，(a, b, c) 和 (x, y, z) 从 M 中删除，并在适当位置形成一个新元组：E := (a + x, b + y, c + z)。元组按其最小值归一化并按降序排序，然后按顺序将其插入 M 中。在每个步骤中，算法通过将旧值（[a, x], [b, y], [c, z]）和用于归一化的数字放入两个堆栈中来记忆旧值数组。

阶段2：

第二阶段从产生的差异集、记忆的旧值和归一化数字构建分区。

在每一步，它都会弹出记忆的旧值数组和规范化编号：

对于旧值数组中的每个元组，它计算一个要在 M 中搜索的值：

然后在 M 中搜索包含该值的分区并将该值替换为元组：

在每次迭代中，它永远不会将两个元组放入同一个分区。所以 [0,1] 进入最后一个分区：

等等：

问题来了：

在这次迭代中，我已经将 [10,0] 元组放入了 [3,2,0,0] 分区，所以我不能再将另一个元组放入其中。但是 M 没有另一个包含值 2 的分区。

如果在出现这种情况时允许将多个元组放入同一个分区，那么我得到的分区远非最佳：

[[0,0,0,0,5,7],[0,0,0,0,0,0,10,9],[1,0,0,3]]

我想我可以使用最大二分匹配来解决这个问题，但感觉就像一个肮脏的黑客。

我错过了一些重要的步骤还是有更好的方法来重建分区？

结论：

David Eisenstat 在 C++ 中提供了该算法的优雅且快速的 OOP 实现。

但是对于我的工作，我需要用 PHP 重写它。实现的直接翻译被证明是内存效率低且速度慢。由于将每个数字包装到 Subset 对象中，因此内存效率低下。而且它很慢，因为在 PHP 中对对象数组进行排序比对数字数组进行排序要慢一个数量级。例如，使用这种方法将 500000 个数字的数组划分为 100 个子集需要 138 秒，而我的贪心算法的实现只需要 9 秒。

因此，在分析器中使用两天后，我使用数组重写了 PHP 实现。它看起来很难看，但是当 k 低时它比我实现的贪婪算法更好，而当 k 高时它不会那么慢：

我希望 David Eisenstat 的答案和我的解决方案都证明是有用的。

我有一个对象列表，bag其中包含Quantity,Volume和weight. 我想在用户输入上拆分或连接多个对象，这将是max weightand max volume，因此我们希望将列表bag进一步拆分为更多bag，以最佳方式由用户提供最大重量和最大体积，以便没有袋子的重量和体积离开了。到目前为止，我所取得的成就是，bag根据volumeorweight拆分，所以首先我根据weight并且完全优化，但是当我应用相同volume的算法来拆分拆分时并不是最好的。我应用的算法：

1. 插入所有bag优先队列
2. 取出每个数量重量最小的第一个元素并将其插入袋子中。
3. 如果袋子已满，请创建一个新袋子，或者轮询下一个袋子并将其也插入。
4. 如果一个包不能完全插入，则划分数量并插入可以插入的数量，其余的保留在优先队列中。

包类

我在面试时遇到了这个问题，似乎无法思考如何解决它。我还没有找到任何解释其背后逻辑的教程。

拥有函数ArrayChallenge(arr)，获取其中存储的整数数组，arr其中始终包含偶数个整数，并确定如何将它们拆分为两个偶数集，然后返回第一个集合的字符串表示形式，然后返回每个整数的第二个集合用逗号分隔，两组均按升序排序。首先出现的集合是第一个整数最小的集合。

例如如果 arr 是 [16,22,35,8,20,1,21,11]，那么你的程序应该输出 1,11,20,35,8,16,21,22

[16,22,35,8,20,1,21,11] 总和 = 134

1,11,20,35 之和 = 67 8,16,21,22 之和 = 67

两个数组的大小也等于 arr.length /2

如何将 N 个整数分成 M 个大小相等的组，以使它们的最大和最小和之间的差最小？

我看到它属于分区类型的问题，但我没有找到同时符合“M > 2”和“大小相等”标准的解决方案

它是工作代码，它是从数据库中转储表，但我要求从表中转储特定行，所以我应该在这个查询中写什么“mysqldump -u admin -p mydvc4408 dvs configuration_files -r”+filepath”

公共类备份{

}