sorting structure

[shankhs]

I am trying to solve a typical 0/1 knapsack problem (using greedy algorithm). In this problem I have to sort a structure consisting of 2 ints (one that contains the value and their corresponding amount I have to minimize the value to get `n' amounts so i need to sort) I am not able to do so.Please help me out.
Please tell me if there exist any better coding method to solve greedy knapsack problem.

[shankhs]

I dont want to use qsort.

[ddanbe]

Have you read : http://en.wikipedia.org/wiki/Knapsack_problem ?

so i need to sort) I am not able to do so.Please help me out.

Why are you not able to do so? Please explain.

[shankhs]

100 5
5 20
9 40
3 10
8 80
6 30

The first line first integer is the amount of milk that I want per day and The second, is the number of farmers that I may buy from. The next lines contain the cost of milk and the max amount of milk that farmer can supply.
I am making a struct whilch contains cost and amt(amount that a farmer can supply) , I want to minimise the cost to buy the given amount of milk .I am sorting this structure as

struct str
{
	int cost;
	int amt;
};
typedef struct str tc;
tc * sort(tc cases[],int n)
{
	for(int j=1;j<n;j++)
	{
		int key=cases[j].cost;
		int k=cases[j].amt;
		i=j-1;
		while(i>=0&&key<=cases[i].cost)
		{
			if(key<cases[i].cost)
			{
				cases[i+1].cost=cases[i].cost;
				cases[i+1].amt=cases[i].amt;
			}
			else if(key==classes[i].cost)
			{
				if(cases[i].amt>k)
				{
				cases[i+1].cost=cases[i].cost;
				cases[i+1].amt=cases[i].amt;
				}
			}
			i=i-1;
		}
		cases[i+1].cost=key
		cases[i+1].amt=k;
	}
	return cases;
}

The sorting(insertion sort) is done wrt the first field if the first field is equal in two cases the second field decides which one will come first.
My main problem is in declaration and calling,actually I am learning to handle pointers so I am not very good at it I am calling the above method as

tc cases[no_far];//no_far==no of farmers
	for(int i=0;i<no_far;i++)
	{
		cin>>cases[i].cost>>cases[i].amt;
	}
	cases=sort(cases,no_far);

Please help,

[ddanbe]

Here is my implementation of a selection sort(in C#)

static void StraightInsertionSort(int[] listtosort)        
{            
 int element;           
 int ic;  //index of element to be compared, index starts at 0

 //loop trgh each element in turn                      
for (int loopvar = 1; loopvar < listtosort.Length; loopvar++) 
{                
  element = listtosort[loopvar];                
  ic = loopvar-1;                
  while (ic >= 0 && listtosort[ic] > element )                 
  {   
    //move all elements                                     
    listtosort[ic + 1] = listtosort[ic]; 
    ic--;                
  }                
  listtosort[ic + 1] = element;    //Insert element            
}                   
}

I see a difference in the while loop. I know my code works, yours will too, carry on!

[ArkM]

I don't understand what for C# code appeares here. There are a lots of insertion (and others) sort C codes in INET. For example, that's one from the excellent tutorial
http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_sorting.aspx#insert

void jsw_insertion ( Str a[], int n )
{
    int i;

    for ( i = 1; i < n; i++ ) {
        int j, save = a[i];

        for ( j = i; j >= 1 && a[j - 1] > save; j-- )
            a[j] = a[j - 1];

        a[j] = save;
    }
}

Now look at the a[j - 1] > save condition. Change all int type for structured variables (not for index variables, of course) to your tc type. So the insert condition must be as follows:

(a[j - 1].cost > save.cost || (a[j - 1].cost == save.cost && a[j-1].amt > save.amt))

That's all. No need to assign structures by elements.

It seems there is a subtle defect in the presented code. You don't break inner loop after key == cases[i].cost (and have misprint there) but the second member test gets false. It's case <= save situation but the inner loop continued...

[ddanbe]

I don't understand what for C# code appeares here

Hey ArkM, no offense intended.
But be it C, C++ or C# basically they are all the same. I am more proficient in C# than in C, so I expressed myself that way.
Google this latin from my signature : Cave ab homine unius libri.

[ArkM]

ddanbe, I'm indifferent to C#, Java, C++, Ada, Fortran, PL/I or what else codes on C forum for beginners. And shankhs? Let he/she gets the feel of new language (that's C)...

Best regards

[shankhs]

Let [B]he/she[/B] gets the feel of new language (that's C)...

I am he.Thanks for pointing out the errors.Am I declaring the function and calling it correctly?

[ArkM]

Nearly correctly ;) : no needs in returned value of a sort function. The only useful and desired effect is sorted array. But it's a parameter of the function so no doubt - it's sorted. Declare this function with void (nothing) returned "value" (see an example).

Rewrite and debug corrected code then come back ;)...