use*_*185 12 algorithm math combinatorics
我遇到了一个有趣的编程问题,我似乎无法制定解决方案.假设你有N种不同颜色的K球.您必须将所有球分成尽可能多的组,这样两个组就不会相同.(如果每组颜色的球数相同,则认为两组相同.)您可以制作的最大组数是多少？
约束:1 <= K <= 50,1 <= N <= 14
澄清:我们想要一个算法,它接受一个整数数组> = 1.数组的大小为N,它包含的值之和为K.算法应返回最大组数.
关于这个问题的算法方法的任何想法？
再次与我的教授交谈后，我了解到这是对 open.kattis.com问题的改编。
两者几乎相同，因为原始问题的任何实例都可以通过对 N 进行素因式分解并将每个素因数视为一个球来解决。例如，900 = 2^2*3^2*5*2，因此等效球问题将是 2 2 2。
给定的边界是使用最大边界 10^15 找到的。2^50 > 10^15，因此因子永远不会超过 50 个，并且前 15 个素数彼此相乘也会超过 10^15，这意味着最多可以有 14 个组。
然而，球的数量和组的数量之间的权衡被忽视了，在我看来，这使得问题更容易解决。例如，如果有 14 组，则每组中只有 1 个球，而如果有 50 个球，则它们都属于同一组（这是由于原始问题的 10^15 约束）
有了这些新信息，我就能解决问题。我将 N 分解为素数列表以及所有因子的列表，然后使用多维背包算法（如果 N 有 X 个唯一素数因子，则背包 DP 将是 X+1 维，其中第一个维度是您正在考虑的项目以及每个其他维度代表您对某个主要因素的剩余供应）。N 的每个因子都代表背包中可能携带的物品，其质因数分解是其成本向量。
这样做之后，问题在最大情况下仍然太慢，需要进行一项额外的优化。我发现始终存在使用尽可能多的单个球组的最佳解决方案。通过在一开始创建尽可能多的 1 球组并解决剩余的子问题，我能够在 Kattis 的时间限制内完成该问题。
我的算法取决于我已经证明的两个假设：
如果您可以在不使用所有球的情况下制作 X 组，那么您也可以使用所有球制作 X 组。这使得未使用 100% 容量的背包解决方案有效。这个假设可以通过取出所有未使用的球并将它们全部添加到最大的组中来证明。这将创建一个比任何其他组都大的组，因此它必须是唯一的。这使您拥有相同数量的组，但使用了所有球。
总是存在使用尽可能多的 1 球组的最佳解决方案。这使得可以将原始问题简化为可在时间限制内解决的子问题。这也可以证明。取任意最优解。对于任何不存在的 1 球分组，取一个包含该 1 球的组，并将该组中的所有其他球移动到最大的组。这将创建一个具有相同（最佳）组数的解决方案，并且还具有尽可能多的 1 球组。
我的解决方案的运行时间为 O(F(N)^2)，其中 F(N) 是 N 的因子总数。