- 论坛徽章:
- 0
|
本帖最后由 ruslin 于 2011-10-10 09:16 编辑
类似背包问题,满二叉树结构。
原理:
比如一共有N个数,参照值是M。那么对于第N个数来说,只有两种选择要么不用这个数,要么就用这个数。
不用的情况就是前N-1个数任意几个数的和最接近M的值是:f(N-1,M), 前N-1个数。
用的情况先算出前N-1个数任意几个数的和最接近M-value(N)的值是:f(N-1,M-value(N)), value(N)显然就是第N个数的值,既然用了它就要把它减了,然后把算出来的值加上value(N)跟不用的情况算出来的值同M相比较,看谁更接近。
n-1,n-2,。。。3,2,1原理都一样。
到了第1个数,求它和某个值x的最接近的值就是两个可能:可以选择它加上value(1),或者不选择它加上(0)。但是left_most节点必须选择。
时间复杂度O(2^n)
存在问题:
1。 递归调用,如果N太大,会调用 2^n - 1次,可能会栈溢出,不知能否去掉递归。
2。 考虑到题目是顺序排列的,不知能否优化,暂时没想到。
3。 测试了几组数据是正常工作的。不保证一定正确。
欢迎指教》
#include <stdio.h>
#include <stdlib.h>
int a[10] = {4, 10, 30, 33, 39, 58, 200, 300, 400, 1000};
int m = 100;
int fun(int n, int value, bool left) {
if (n == 0) {
//n == 0 && left=true, 这个节点就是left_most节点。
if (!left && abs(0 - value) < abs(a[0] - value)) {
return 0;
} else {
return a[0];
}
}
int value1 = fun(n-1, value, left ? true : false);
int value2 = fun(n-1, value-a[n], false);
//printf("fun n = %d, value = %d, value1 = %d, value2 = %d\n", n, value, value1, value2);
if (abs(value2 + a[n] - value) < abs(value1 - value)) {
printf("fun n = %d, value = %d, value2 = %d, a[%d] = %d, res = %d\n", n, value, value2, n, a[n], value2 + a[n]);
return value2 + a[n];
} else {
printf("fun n = %d, value = %d, res = %d\n", n, value, value1);
return value1;
}
}
int main() {
int res = fun(sizeof(a)/sizeof(a[0])-1, m, true);
printf("res = %d\n", res);
return 0;
}
root@ubuntu:/work# ./a.out | grep "value = 100"
fun n = 1, value = 100, value2 = 4, a[1] = 10, res = 14
fun n = 2, value = 100, value2 = 14, a[2] = 30, res = 44
fun n = 3, value = 100, value2 = 44, a[3] = 33, res = 77
fun n = 4, value = 100, value2 = 63, a[4] = 39, res = 102
fun n = 5, value = 100, value2 = 43, a[5] = 58, res = 101
fun n = 6, value = 100, res = 101
fun n = 7, value = 100, res = 101
fun n = 8, value = 100, res = 101
fun n = 9, value = 100, res = 101 |
|