Just read the comments. You will get logic. 1> read global variables 2> start with main 3> read rec (a recursive fn)
The main logic is that whether to keep the no in the final no (by decrementing it) or to completely remove it. #include <stdio.h> #define SIZE 4 int result[SIZE]; /*Array for storing current state of solution*/ int final_cost = 100000; /*set minimum cost to some large value*/ int curr_ans[SIZE]; /*sorted array with the minimum cost*/ /*copies result into curr_ans*/ void save_arr(int *result) { int i; for (i=0 ;i<SIZE ;i++) { curr_ans[i] = result[i]; } } /*print the final solution*/ void print_ans() { int i; for (i=0 ;i<SIZE ;i++) { printf (" %d",curr_ans[i]); } } void rec (int *arr,int index,int min,int cost) { if (index >= 0) { /* * keep the arr[index] in the solution * i.e copy arr[index] in curr_ans[index] * will increase cost by * 1> arr[index] - min if arr[index] > min * (where min is the min no among arr[index] to arr[SIZE-1]) * 2> 0 if arr[index] < min and will set min = arr[index] * (where min is the min no among arr[index] to arr[SIZE-1]) * * After this call a fn rec (recursively) with index-1 * new cost calculated and new min */ if (arr[index] <= min) { result[index] = arr[index]; rec (arr,index-1,arr[index],cost); } else { result[index] = min; cost += (arr[index] - min); rec (arr,index-1,min,cost); cost -= (arr[index] - min); } /* * remove the arr[index] from the solution * copy 0 in curr_ans[index] increases the * cost by arr[index] as we are removig it */ result[index] = 0; cost += arr[index]; rec (arr,index-1,min,cost); } else if (index == -1) { if (cost < final_cost) { final_cost = cost; save_arr(result); } return; } } int main(int argc,char *argv[]) { int i; int arr[SIZE] = {10,3,11,12}; rec(arr,SIZE-1,arr[SIZE]+1,0); /* * start with the last index i.e traverse array from end to start * as we call rec with index-1 each time */ printf ("\n minimum cost = %d \n sorted array =",final_cost); print_ans(); return 0; } On Sun, Aug 29, 2010 at 2:18 PM, jagadish <jagadish1...@gmail.com> wrote: > > @Rahul Patil: > I ran your code on some basic test cases and i found it to be > correct! > > Can you please explain the logic you used to arrive at the solution? > > Thanks :-) > > On Aug 29, 12:25 pm, rahul patil <rahul.deshmukhpa...@gmail.com> > wrote: > > check out this solution.I think this works correct > > will explain logic if u find it correct. > > > > #include <stdio.h> > > #define SIZE 4 > > int result[SIZE]; > > int final_cost = 100000; > > int curr_ans[SIZE]; > > > > void save_arr(int *result) > > { > > int i; > > for (i=0 ;i<SIZE ;i++) { > > curr_ans[i] = result[i]; > > } > > > > } > > > > void print_ans() > > { > > int i; > > for (i=0 ;i<SIZE ;i++) { > > printf (" %d",curr_ans[i]); > > }} > > > > void rec (int *arr,int index,int min,int cost) > > { > > if (index >= 0) { > > // keep the arr[index] > > if (arr[index] <= min) { > > result[index] = arr[index]; > > rec (arr,index-1,arr[index],cost); > > } else { > > result[index] = min; > > cost += (arr[index] - min); > > rec (arr,index-1,min,cost); > > cost -= (arr[index] - min); > > } > > > > // remove the arr[index] > > result[index] = 0; > > cost += arr[index]; > > rec (arr,index-1,min,cost); > > } else if (index == -1) { > > if (cost < final_cost) { > > final_cost = cost; > > save_arr(result); > > } > > return; > > } > > > > } > > > > int main(int argc,char *argv[]) > > { > > int i; > > int arr[SIZE] = {10,3,11,12}; > > rec(arr,SIZE-1,arr[SIZE]+1,0); > > printf ("\n minimum cost = %d \n sorted array =",final_cost); > > print_ans(); > > return 0; > > > > } > > > > On Aug 29, 1:17 am, Neeraj Gupta <neeraj.gu...@nsitonline.in> wrote: > > > > > On Sun, Aug 29, 2010 at 1:35 AM, Gene <gene.ress...@gmail.com> wrote: > > > > My algorithm proposal wasn't correct, but I can't see how to get 8. > > > > You need to decrement 14, 15, 16, 13 to 11. This costs 14. > > > > > > So do I. > > > > > May be he has not noticed that incrementing a number is not an option. > ;) > > > > > > On Aug 28, 5:41 am, gaurav singhal <singhal08gau...@gmail.com> > wrote: > > > > > @ Gene : > > > > > > > Output for > > > > > > > int a[] = { 14, 15, 16, 13, 11, 18 }; > > > > > > > is coming out to be 14 > > > > > > > whereas minimum cost will be : 8 > > > > > > -- > > > > 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<algogeeks%2bunsubscr...@googlegroups.com> > <algogeeks%2bunsubscr...@googlegroups.com<algogeeks%252bunsubscr...@googlegroups.com> > > > > > > . > > > > For more options, visit this group at > > > >http://groups.google.com/group/algogeeks?hl=en. > > -- > 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<algogeeks%2bunsubscr...@googlegroups.com> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- Regards, Rahul Patil -- 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.