Member Avatar for thompsonSensibl

Hi there... A little mental blockage ='-(

The scenario:
1. A thief has a bag that cannot be larger than 5m^3.
2. He is a superman, and he can carry ANY amount.
3. He finds piles of valuable powders. He plans to steal them... naughty naughty.

4. Each pile is of a DIFFERENT powder, with its unique volume (in m^3), value (per gram), and
density (in grams per cm^3).

His goal is to steal as much as high bag allows (size-wise of course, cuz the weight isn't an
issue) with the highest value.

NOW, my question:
How can I determine which piles he should take?
(Yes, the obvious answer is, "take as much of the most valuable powder as he can"; yes, but how do you determine that, mathematically?

I am so hopeless at maths; please help and allow me to sleep!
Thank you

  • 4 Contributors
  • 4 Replies
  • 85 Views
  • 4 Days Discussion Span
  • Latest Post Latest Post by Momerath
Member Avatar for Narue

Yes, the obvious answer is, "take as much of the most valuable powder as he can"; yes, but how do you determine that, mathematically?

Is there a variable for powder value, or are you simply using size?

Member Avatar for TrustyTony

From value/g and g/cm3 calculate value/cm3 and decide based on this. Can he take any amount he likes or must he take all the pile of powder?

Edited by TrustyTony because: n/a
Member Avatar for thompsonSensibl

From value/g and g/cm3 calculate value/cm3 and decide based on this. Can he take any amount he likes or must he take all the pile of powder?

Makes sense, but how do you do that? "calculate value/cm3"...?

Also, yes, he can take any amount he likes; does not need to take the whole amount.

Member Avatar for Momerath

This is not the Knapsack problem as you only have one constraint (volume).

Calculating value/cm3 is easy: You have value/gram and gram/cm3. Multiply the two and you get value/cm3 (the grams cancel).

Sort high to low (or use the Heapify function of heapsort which would be faster, but probably overkill unless you have thousands of items :)) and take what you can until the bag is full.

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.