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.

## All 9 Replies

I dont want to use qsort.

``````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);``````

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!

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...

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.

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

commented: Carry on with the good cause. You're right it was a slip of my tongue, it had to be C here and nothing else. +2
``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?

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 ;)...

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.