GREEDY ALGORITHM in Pascal

[joydivision]

Hi guys,I've been having some problems with this one since I'm only a beginner.

There's a thief in the grocery store with a multiple boxes of fruits and vegetables.
Each boxs has a weight given in kilograms and the value per each kg of the item from that box.
The thief cannot carry more than m (variable) kilograms.
He doesn't have to take the whole box.He can as well take a smaller amount of fruits or vegetables from it.
What is the biggest profit that the thief can make in a given situation?

n- number of the boxes
x- weight
y- price of the items in the box per kg
m- number of kgs he is able to take out

I'm not really sure about the assign-s and the code.
Thanks in advance!

[Blaazen]

I would select the box with the highest y and take as much as he can (i.e. less then m).
Then select box with the second highest y and take as much as he can (m minus what he already have).
And so on.

[engkin]

And the biggest profit would be the sum of (y of a box) * (how many kilograms was taken from that box).

[Leledumbo]

The biggest hint is that you're learning greedy algorithm. So, simply take the best value at each step would yield the best result.

[engkin]

Its always nice to have informational post on discussion boards which helps individuals to get all the relevant info which he/she may be looking for.

It sounds like a good idea. Do you have anything you want to add here? 

[avra]

There's a thief in the grocery store with a multiple boxes of fruits and vegetables.

Are you asking us to help a thief?   

_{Sorry, just couldn't resist!} 

[CaptBill]

There's a thief in the grocery store with a multiple boxes of fruits and vegetables.

Are you asking us to help a thief?   

_{Sorry, just couldn't resist!} 

Bad news, Avra.
I think Xe's calling you one.

[joydivision]

I would select the box with the highest y and take as much as he can (i.e. less then m).
Then select box with the second highest y and take as much as he can (m minus what he already have).
And so on.

Thank you so much!
Could you please write the code for it?   
That is the problem I'm having.
I understand it but I cannot really put it into code.


Thanks again!

[joydivision]

There's a thief in the grocery store with a multiple boxes of fruits and vegetables.

Are you asking us to help a thief?   

_{Sorry, just couldn't resist!} 

I thought the task was rather weird when I got it,too. 

[typo]

There is a lack of information, such as the number of items on each box.

Basically you need to sort the items by Y (price) and get them from the top until the weight is M.

[CaptBill]

There's a thief in the grocery store with a multiple boxes of fruits and vegetables.

Are you asking us to help a thief?   

_{Sorry, just couldn't resist!} 

I thought the task was rather weird when I got it,too. 

Better run on back to corporate, JoyDivision.

[marcov]

Hi guys,I've been having some problems with this one since I'm only a beginner.

There's a thief in the grocery store with a multiple boxes of fruits and vegetables.
Each boxs has a weight given in kilograms and the value per each kg of the item from that box.
The thief cannot carry more than m (variable) kilograms.
He doesn't have to take the whole box.He can as well take a smaller amount of fruits or vegetables from it.
What is the biggest profit that the thief can make in a given situation?

Isn't that the NP complete knapsack problem?

Ian Curtis.

[Leledumbo]

Isn't that the NP complete knapsack problem?

I don't think so, since only biggest profit is asked. It's a 0-1 knapsack. Just forget the box, it's a confuser.

[typo]

I think that "price of the items per Kg" makes the two problems be different. Maybe the "Greedy Approximation Algorithm". I don't know any implementation in Pascal.

[CaptBill]

If he understands scaling and is programming in LAZARUS, you might fit in the palm of his hand, JoyDivision.

http://upload.wikimedia.org/wikipedia/commons/9/91/Orion_constelation_PP3_map_PL.jpg