https://community.topcoder.com/stat?c=problem_statement&pm=1166&rd=4705
https://blog.csdn.net/makeway123/article/details/45583645
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
https://blog.csdn.net/makeway123/article/details/45583645
给定一个数组,要把这个数组中的一部分数给A,另一部分给B,使A和B的和相同但是A中最小的数不小于B中最大的数。例如:
values = {1,2,5,3,4,5}
一共有9中分配方法:
Bob Frank
1,2 3
1,3 4
1,4 5 (first 5)
1,4 5 (second 5)
2,3 5 (first 5)
2,3 5 (second 5)
5 (first 5) 5 (second 5)
5 (second 5) 5 (first 5)
1,2,3,4 5,5
1,2 3
1,3 4
1,4 5 (first 5)
1,4 5 (second 5)
2,3 5 (first 5)
2,3 5 (second 5)
5 (first 5) 5 (second 5)
5 (second 5) 5 (first 5)
1,2,3,4 5,5
需要注意的是不同位置的相等数字需要单独计算。数组大小最大30,每个数最大1000。
// Maximum sum that can be formed.
int MAX_SUM = 30000;
// Maximum no of jewelery items.
int MAX_ELEMENT = 30;
// cache for the binmoial coefficient n choose k.
long[][] comb = new long[MAX_ELEMENT + 1][MAX_ELEMENT + 1];
public long howMany(int[] values) {
Arrays.sort(values);
long ret = 0;
int groupSize = 1;
for (int i = 0; i < values.length - 1; i += groupSize) {
long[] waysBelow = getSumWays(Arrays.copyOfRange(values, 0, i));
groupSize = 1;
for (int j = i + 1; j < values.length; j++) {
if (values[j] != values[i])
break;
groupSize++;
}
for (int g = 0; g < groupSize; g++) {
long[] waysAbove = getSumWays(Arrays.copyOfRange(values, i + g + 1, values.length));
for (int s = values[i] * (g + 1); s <= MAX_SUM; s++) {
ret += (comb(groupSize, g + 1) * waysBelow[s - values[i]*(g+1)] * waysAbove[s]);
}
}
}
return ret;
}
long[] getSumWays(int[] values) {
int maxSum = sum(values);
long[] ways = new long[MAX_SUM + 1];
ways[0] = 1;
for (int i = 0; i < values.length; i++) {
for (int j = maxSum; j >= values[i]; j--) {
ways[j] += ways[j - values[i]];
}
}
return ways;
}
int sum(int[] values) {
int sum = 0;
for (int i = 0; i < values.length; i++) {
sum += values[i];
}
return sum;
}
long comb(int n, int k) {
if (comb[n][k] > 0)
return comb[n][k];
if (k == 0 || n == k)
return 1;
comb[n][k] = comb(n - 1, k - 1) + comb(n - 1, k);
return comb[n][k];
}