客户有如此需求,不知道是懒,还是正常。感觉有难度。哈哈请大家帮忙分析一下。先谢谢。需求:财务部经常收到某客户几个合同的汇款,所以他们要人工去一个个找,可能正好等于,或某几个合同的款项。或最接近的某几个合同(有预付款的情况)比如 某客户 A 共有6个合同
A001 123.4元
A002 200元
A003 300元
A004 350元
A005 450元
A006 500元情况一(某数相等)、
客户汇款为:200元 那么对应合同号:A002
情况二(某几个数相加相等)、
客户汇款为:423.4元 那么对应合同号:A001、A003
情况三(某个数或某几个数之和最接近)、
找出最接近的参考合同。请大家帮忙分析一下。
A001 123.4元
A002 200元
A003 300元
A004 350元
A005 450元
A006 500元情况一(某数相等)、
客户汇款为:200元 那么对应合同号:A002
情况二(某几个数相加相等)、
客户汇款为:423.4元 那么对应合同号:A001、A003
情况三(某个数或某几个数之和最接近)、
找出最接近的参考合同。请大家帮忙分析一下。
A:206
B:{a:100 b:150 c:200 d:300 e:400 f:600 g:802}
输入一个数A 找出在指定 数组里B 中任意 几个数值的和 的下标.
B排序;
C取B中间的值:300 下标:dA 大于 C 往右进行折半查找,找到刚好等于的就输出下标 比最后的值还大就.....组合查找,否则就取当前下标-1和当前下标+1
小于一样;
不知道是不是这样做o.
客户汇款为:200元 那么对应合同号:A002
@lz: 这个简单,直接查找情况二(某几个数相加相等)、
客户汇款为:423.4元 那么对应合同号:A001、A003情况三(某个数或某几个数之和最接近)、@lz: 情况2与3实际上是一个问题,就是误差的设置而已:
1. 把数组从小到大排序
2. 找到与第一个数的和小于等于输入的元素下标end
3. 然后对从0到end取所有元素的组合求和
4. 找到和里面最接近的就可以了。因为这个组合的个数是不定的,所以必须要列举出所有的情况。
但是因为求组合的性能问题,总共的个数每增加一个,计算都是爆炸式增加,所以对数据的组织要分类,查询的时候也要分类来查询。
下面的代码是我使用的组合算法,作一点点修改就可以用了。
package test;/**
* 求 N 个元素的全排列算法:
* 1. 创建一个大小为 N 个元素的数组.
* 2. 利用 N 进制,满 N 加 1的原则,对数组的第0个元素加 1,满 N 了,则下一个元素值加 1.
* 3. 检查数组中的元素是否有重复的,如果没有,则是一个排列.
* 4. 直到数组中的元素为0, 1, 2, ..., N - 1,则结束,否则继续第2步直到结束.
*//**
* 求 N 个元素中 M 个元素的组合算法:
* 1. 创建一个大小为 N 个元素的数组,前 M 个元素为1,后面的 N-M 个元素为0
* 2. 从左向右找到 10 的元素(前一个元素是1,下一个元素是0), 交换这两个元素;
* 把此元素前面的所有1都移动到数组的最前面,此为一个组合,输出.
* 3. 直到前 N-M 个元素都为0,则结束,否则继续第2步直到结束.
*/
public class Combinatory {
public static void produceCombination(String str, int size) {
if (size > str.length()) { throw new IllegalArgumentException("Size is to large."); } // 创建一个数组,前size个元素全是1
int[] digit = new int[str.length()];
for (int i = 0; i < size; ++i) {
digit[i] = 1;
} // 输出第一组
printCombination(str, digit); while (!end(digit, digit.length - size)) {
for (int i = 0; i < digit.length - 1; ++i) {
if (digit[i] == 1 && digit[i + 1] == 0) {
// i上是1,i + 1是0,交换
int temp = digit[i];
digit[i] = digit[i + 1];
digit[i + 1] = temp; // 移动i前面的所有1到最左端
int count = countOf1(digit, i);
for (int j = 0; j < count; ++j) {
digit[j] = 1;
} for (int j = count; j < i; ++j) {
digit[j] = 0;
} printCombination(str, digit); break;
}
}
}
} // 在下标end前1的个数
private static int countOf1(int[] digit, int end) {
int count = 0;
for (int i = 0; i < end; ++i) {
if (digit[i] == 1) {
++count;
}
} return count;
} // 数组中为1的下标对应的字符需要输出
private static void printCombination(String str, int[] digit) {
StringBuffer sb = new StringBuffer();
for (int i = 0; i < digit.length; ++i) {
if (digit[i] == 1) {
sb.append(str.charAt(i));
}
} System.out.println(sb);
} // 结束条件:前 size 个元素都是0
private static boolean end(int[] digit, int size) {
int sum = 0; for (int i = 0; i < size; ++i) {
sum += digit[i];
} return sum == 0 ? true : false;
} public static void main(String[] args) {
System.out.println("Start");
String str = "0123456789abcdef";
long appStart = System.currentTimeMillis();
long elapse = 0;
for (int i = 1; i <= str.length(); ++i) {
long start = System.currentTimeMillis();
Combinatory.produceCombination(str, i);
elapse = System.currentTimeMillis() - start;
System.out.printf("Millis: %d, Seconds: %d\n", elapse, elapse / 1000);
}
elapse = System.currentTimeMillis() - appStart;
System.out.printf("Total Millis: %d, Seconds: %d\n", elapse, elapse / 1000);
}
}