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 <[email protected]> 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 <[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]>
> <algogeeks%[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]<algogeeks%[email protected]>
> .
> 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 [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.
