给定数字N和M,则从数字1到N得序列中添加+或-
,使得序列的和最接近M,打印出所有满足此关系的序列,例如,给定N=4 M=6
,则满足条件得序列是1-2+3+4=6
;
看到这样得题目,第一反应是动态规划,对于每一个数,其有两种取法,+或-
,则依次遍历所有得数,尝试这两种可能,最后得出结果。动态规划需要列出详细的递归表达式,定义出递归表达式得意义,给出边界条件,记录递归过程中得中间结果,知道在什么情况下,递归结束。
首先列出递归表达式,F(i,m)
表示数组前i的元素通过添加加减号后与整数M之间最小得差距,例如对于上面给出得例子,F(3,6)=0
> F(i,m) = min{|F(i-1,m-a[i])|,|F(i-1,m+a[i])|} ( 0<= i < n)
除了上面得表达式之外,还需要一个二位数组记录中间结果。
根据前面的动态规划分析,则可以按照递归表达式来写出方程。在记录中间结果的时候,target-array[i]可能小于0了,所以使用了一个offset偏移量,保证前面的能够大于0。因为是记录前i个数通过添加加减号之后与M的差距,故只记录绝对值。
int dfsV4(const int* array, int index, int target,int offset, int **state){
if(index == 0){
return abs(target-1,0) < abs(target+1,0) ? target - 1 : target + 1;
}
if(state[index][target+offset] > INT_MIN)
return state[index][target+offset];
int plus = dfsV4(array,index-1,target+array[index],offset,state);
state[index-1][target + array[index] + offset] = plus;
int minus = dfsV4(array,index-1,target-array[index],offset,state);
state[index-1][target - array[index] + offset] = minus;
state[index][target+offset] = abs(plus,0) < abs(minus,0) ? abs(plus) : abs(minus);
return state[index][target+offset];
}
此题的动态规划过程很简单,按照表达式来实现就行了,然后是进行回溯,打印出所有存在的可能组合,
void backtracing(const int *array, int index, int **state, int offset, int target,stack<bool> symbol){
if(index == 0){
if(abs(target + 1,0) < abs(target - 1,0))
symbol.push(true);
else
symbol.push(false);
int i = 0;
while(!symbol.empty()){
if(!symbol.top()){
if(i == 0){
cout << array[i++];
}else{
cout <<"+"<< array[i++];
}
}else{
cout << "-" << array[i++];
}
symbol.pop();
}
cout << endl;
return;
}
int left = state[index-1][target-array[index] + offset];
int middle = state[index][target+offset];
if(middle == left){
symbol.push(false);
backtracing(array,index-1,state,offset,target-array[index],symbol);
}else{
symbol.push(true);
backtracing(array,index-1,state,offset,target+array[index],symbol);
}
int right = state[index-1][target+array[index] + offset];
if(middle == left && middle == right){
symbol.pop();
symbol.push(true);
backtracing(array,index-1,state,offset,target+array[index],symbol);
}
}
测试此代码,给定N = 4,M = 6
,则是在1,2,3,4中查找与6最接近得组合。运行结果如下:
1-2-3+4+5
1+2+3-4+5
1+2+3+4-5
虽说有了正确得结果,但是总感觉,还可以定义其他得递归表达式,使思路看上去更加明了和清晰!欢迎大家指导!
关于这个题目得变形有很多,大概都是在数组构造出和为某个值的子序列。例如
在数组中查找和为M的子序列。
将数组划分为和相差最小的两个子数组