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.
