@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 <[email protected]> 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 <[email protected]> wrote: > > > On Sun, Aug 29, 2010 at 1:35 AM, Gene <[email protected]> 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 <[email protected]> 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 [email protected]. > > > To unsubscribe from this group, send email to > > > [email protected]<algogeeks%[email protected]> > > > . > > > 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
