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?

Thank you

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?

## All 4 Replies

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?

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?

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.

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 1.21 million developers, IT pros, digital marketers, and technology enthusiasts learning and sharing knowledge.