如何将整数数组划分为2个子数组并使它们的平均值相等？

Question

请帮助我解决上述问题.将会感谢具有工作示例的算法.此外,如果无法满足上述要求,请处理此案.

好的,我到现在为止的内容如下:

遍历整个数组并获得整个数组的平均值.上).让我们称之为平均值

然后从这个平均值得到整个数组的平均值除外a[0](公式为:) avg(a[1..n-1])=(avg(a[0..n-1])*n-a[0])/(n-1).然后你取这个新的平均值并将其与[0]进行比较.如果它们不相等,则使用上面的公式移动到下一个值,从先前已知的平均值计算平均值.

虽然有人为我提供了"有效"的解决方案,但我正在寻找最有效的实施方案.

Answer 1

快速谷歌搜索返回了这个。无论如何，如果您不追求性能，回溯始终是一个选择

编辑：我尝试应用回溯。我的解决方案毫无效率。当然，您可以替换平均方法以避免另一个级别的循环。另外，为了表明没有解决方案，您可以只计算解决方案的数量。

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;

public class SOQuestion {

    /**
     * just prints a solution
     * 
     * @param list
     * @param indexes
     */
    public static void printSolution(List list, HashSet indexes) {
        Iterator iter = indexes.iterator();
        while (iter.hasNext()) {
            System.out.print(list.get((Integer) iter.next()) + " ");
        }
        System.out.println();
    }

    /**
     * calculates the average of a list, but only taking into account the values
     * of at the given indexes
     * 
     * @param list
     * @param indexes
     * @return
     */
    public static float avg(List list, HashSet indexes) {
        Iterator iter = indexes.iterator();
        float sum = 0;
        while (iter.hasNext()) {
            sum += (Integer) list.get((Integer) iter.next());
        }
        return sum / indexes.size();
    }

    /**
     * calculates the average of a list, ignoring the values of at the given
     * indexes
     * 
     * @param list
     * @param indexes
     * @return
     */
    public static float avg_e(List list, HashSet indexes) {
        float sum = 0;
        for (int i = 0; i < list.size(); i++) {
            if (!indexes.contains(i)) {
                sum += (Integer) list.get(i);
            }
        }
        return sum / (list.size() - indexes.size());
    }

    public static void backtrack(List list, int start, HashSet indexes) {
        for (int i = start; i < list.size(); i++) {
            indexes.add(i);
            if (avg(list, indexes) == avg_e(list, indexes)) {
                System.out.println("Solution found!");
                printSolution(list, indexes);
            }
            backtrack(list, i + 1, indexes);
            indexes.remove(i);
        }
    }

    public static void main(String[] args) {
        List test = new ArrayList();
        test.add(2);
        test.add(1);
        test.add(3);

        backtrack(test, 0, new HashSet());
    }
}