avg(a[1..n-1])=(avg(a[0..n-1])*n-a[0])/(n-1)）。接下来，你需要拿这个新的平均值和a[0]进行比较。如果它们不相等，你就继续计算先前知道的平均值，并使用上述公式进行计算。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());
}
}
回溯），也是如此。要将其作为答案，解释如何解决问题，并将这些链接作为参考资料发布。 - Björn Pollex尝试这段代码...
#include <QList>
#include <QDebug>
/****
We sort the array in the desending order. So the first two elemnts
are the biggest element of the array. These are put in split1 and the
split2 array. Note that we start from the biggest element the average
is going to be much higher than the final avarage. Next we start placing
the smaller elemnts from source to split1 or split2. To do this we make a
simple dicision. We look at the value to be added and then see if that will
increase/decrease the average of a given split. Accordingly we make our
decesion.
****/
static bool averageSplit(const QList<int>& source,
QList<int>& split1,
QList<int>& split2)
{
if (source.size() < 2) {
return false;
}
QList<int> list = source;
qSort(list.begin(), list.end(), qGreater<int>());
double sum = 0;
foreach(int elm, list) {
sum += elm;
}
const double totalAvg = sum / list.size();
double sum1 = list[0];
double sum2 = list[1];
split1.append(list[0]);
split2.append(list[1]);
for(int i = list.size() - 1; i >= 2; --i) {
double avg1 = sum1 / split1.size();
double avg2 = sum2 / split2.size();
int val = list[i];
if (avg1 < avg2) {
// Try to increase tha avg1 or decrease avg2.
if (val > split1.size()) {
split1.append(val);
sum1 += val;
}
else {
split2.append(val);
sum2 += val;
}
}
else {
// Try to increase tha avg2 or decrease avg1.
if (val > split2.size()) {
split2.append(val);
sum2 += val;
}
else {
split1.append(val);
sum1 += val;
}
}
}
qDebug() << "totalAvg " << totalAvg;
qDebug() << "Avg1 " << sum1 / split1.size();
qDebug() << "Avg2 " << sum2 / split2.size();
}
void testAverageSplit()
{
QList<int> list;
list << 100 << 20 << 13 << 12 << 12 << 10 << 9 << 8 << 6 << 3 << 2 << 0;
list << -1 << -1 << -4 << -100;
QList<int> split1;
QList<int> split2;
averageSplit(list, split1, split2);
qDebug() << "split1" << split1;
qDebug() << "split2" << split2;
}
#include<stdio.h>
void partitionEqualAvt(int *a, int n)
{
int i;
int sum=0, sSum=0, eSum, sAvg, eAvg;
for(i=0; i<n; i++)
sum+=a[i];
eSum=sum;
for(i=0; i<n-1; i++)
{
sAvg=0;
eAvg=0;
sSum+=a[i];
eSum=sum-sSum;
sAvg=sSum/(i+1);
eAvg=eSum/(n-i-1);
if(sAvg == eAvg)
{
printf("\nAverage = %d from [%d to %d] and [%d to %d]", sAvg, 0, i, i+1, n);
}
}
}
int main()
{
int a[]={1,1,1,1,1,1};
int n=sizeof(a)/sizeof(int);
partitionEqualAvt(a,n);
return 0;
}
使用贪心算法 解决问题的一种方法是模仿孩子选择游戏队伍的方式，即使用贪心算法。该算法按降序迭代数字，将每个数字分配给较小总和的子集。当集合中的数字与其基数大小相当或更小时，此方法效果良好。
在Python中尝试这样做： 如果平均值存在，则可能找到它，否则它会让你接近平均值。
a = [500, 1, -45, 46, -20, 100, -30, 4, 110]
b, c = [], []
m1, m2, n1, n2 = 0, 0, 0, 0
count = 0
for i in a:
if count == 0:
b.append(i)
n1 += 1
m1 = i
n1 = 1
count = 1
continue
else:
tmp_m1 = (m1 * n1 + i) / (n1 + 1)
tmp_m2 = (m2 * n2 + i) / (n2 + 1)
print b, c, tmp_m1, tmp_m2
if m1 > m2:
if(tmp_m1 - m2 < m1 - tmp_m2):
b.append(i)
m1 = tmp_m1
n1 += 1
else:
c.append(i)
m2 = tmp_m2
n2 += 1
else:
if(tmp_m1 - m2 < m1 - tmp_m2):
c.append(i)
m2 = tmp_m2
n2 += 1
else:
c.append(i)
m1 = tmp_m1
n1 += 1
print b, c, m1, m2
Sample output:
[500] [] 250 1
[500, 1] [] 151 -45
[500, 1, -45] [] 124 46
[500, 1, -45] [46] 108 13
[500, 1, -45, -20] [46] 106 73
[500, 1, -45, -20] [46, 100] 80 38
[500, 1, -45, -20, -30] [46, 100] 67 50
[500, 1, -45, -20, -30, 4] [46, 100] 73 85
[500, 1, -45, -20, -30, 4] [46, 100, 110] 73 73
这是我是如何做到的：
1 - 总数组 --> 如果是奇数，则无法创建两个单独的数组。O(n)
2 - 将总数除以2。
3 - 对数组进行排序（从高到低）--> O(NLogN)
4 - 从最高的数字开始，不断尝试通过转移到下一个最高的数字来获得剩余的金额。如果无法完成，则将该数字移动到另一个数组中。--> 我认为最坏情况是O(N^2)。
所以让我们以这个例子为例： 3, 19, 7, 4, 6, 40, 25, 8
我认为如果原始数组中所有元素的总和是奇数，则无法将其分成两个数组。 但是，如果总和等于偶数，则可以开始制作您的数组，使得每个元素的总和等于SUM/2
O(n)，我认为它不能比这更有效率，因为您必须查看数组的每个元素一次。 - Björn Pollex