(a) it is intuitive to see we need to make a recursive function which
takes the following arguments:
1) array,
2) start index,
3) length of the array,
4) a sentinel indicating if it is the first half or second half
5) a sum if it is the second half
6) number of cuts so far
7) a global minimal cuts
So my recursive function looks something like this,
void cutMinHelper(int *arr, int start, int len, bool isFirst, int sum,
int cut, int &minV, vector<int> &res);
and its wrapper just takes two arguments
void cutMin(int *arr, int len);
The idea is to differentiate the first half and second half. If it's
the first half, you need make all possible cuts, and recursive call
itself to get the second done. If it's the second half, you need
calculate sums all the way to the end. Break out of the loop if it
equals to the sum of the first part. And then recursively call itself
to get the first half done.
I hope my code explains the idea...Please report any bugs you find :)
vector<int> minVector; //storing the cuts
void cutMin(int *arr, int len){
int cut=0, minV = INT_MAX;
vector<int> res;
cutMinHelper(arr, 0, len, true, 0, cut, minV, res);
if(minV<INT_MAX){
cout<<"minimal cut is"<<minV<<endl;
}
}
void cutMinHelper(int *arr, int start, int len, bool isFirst, int sum,
int cut, int &minV, vector<int> &res){
if(isFirst && start<len){
if(start==0) cut = 0;
int sum = arr[start];
cut++;
for(int i = start+1; i < len; i++){
vector<int> addOne = res;
addOne.push_back(i-1);
cutMinHelper(arr, i , len, !isFirst, sum, cut, minV,
addOne);
sum += arr[i];
}
}
if(!isFirst && start<len){
int i, sum2 = 0;
for(i = start; i < len; i++){
sum2 += arr[i];
if(sum2 == sum){
break;
}
}
if( i==len-1 && sum2==sum) {
if(cut<minV){
minV = cut;
minVector = res;
}
}
if(i<len-1){
cut++;
vector<int> addOne = res;
addOne.push_back(i);
cutMinHelper(arr, i+1, len, !isFirst, 0, cut, minV,
addOne);
}
}
}
(b) I didn't write the code, but I think the code would look like the
first one with few modifications.
On Jan 10, 1:08 pm, shady <sinv...@gmail.com> wrote:
> Given an array of numbers : a1, a2, a3..... an....
> (a) divide them in such a way that every alternate segment is given to
> two persons john and mary, equally,,,, the number of segments made should be
> minimum...
> eg....
> for input
> 1 4 5 6 2 2 2 2 4 5 6 1 1 7 8 8 1 7
> segments :
> (John)1 4 5 6 2 2 ----- (Mary)2 2 4 5 6 1 --- (john) 1 7 8 ------ (Mary) 8 1
> 7
> minimum cuts made are 3
>
> (b) Divide the numbers in such a way that both recieve same sum of
> numbers.
> If input
> 3 4 5 7 2 5 2
> segments
> (john) 3 4 5 ----- (mary) 7 2 5 ----- (john) 2
> minimum cuts are 2
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
