有价值的排列

Question

问题:有2个正值A和B大小的并行数组n.

如何找到以下目标函数的最小值:

F(A, B) = Ak + Bk * F(A', B')

其中A',B'表示数组A并删除B它们的k:th元素.

我在考虑动态编程方法,但没有成功.

如何应用于这类问题,我们需要在排列上评估给定的函数？

Answer 1

不是解决方案，但可能是一种启发。看起来F(A, B) = Ak + Bk * F(A', B')很明显F(A', B')会比Ak或更大Bk。因此，由于乘法的原因，我们应该选择Bk尽可能小的值，这将给我们一个值k，因此F(A, B)当我们计算它时，它会是一个可能的最小值。如果有多个最小的，Bk我们可以计算它们并选择最小的。

然后，我们可以启动一个强力算法，遍历所有可能的结果，但我们已经有一个可能的最小结果，因此，如果当前的试验将给我们带来比我们已有的结果更大的结果，我们可以提前终止。