In this problem a thief breaks into a vaultthat has a large collection of gems.

Question

In this problem a thief breaks into a vaultthat has a large collection of gems. The gems are of all types,from very rare diamonds to common stones. The thief has anexperienced eye so she can instantly estimate the value and weightof each gem. In order to sneak away cleanly she carries a smallknapsack that will only take N carats of gems. Her problem is totake the set of gems that in total are most valuable but that stillfit in the knapsack. All weights are in integers (these are alllarge gems). She doesn't have to fill the knapsack exactly - itcould be that the most valuable stones weigh less than N carats butshe cannot add another gem without going over the weigh limit. (Thegeneral case of this problem is simply called knapsack.)

For example, there might be 7 gems,represented as pairs with weight, value: ruby (2 carats, $100);diamond (1 carat, $400); emerald (3 carats, $250); amethyst (2carats, $50); opal (1 carat, $300); sapphire (2 carats, $500);malachite (1 carat, $60). The seven gems total 12 carats, but thethief can only carry 5. Which stones should she take to get themaximum value in dollars?

A paper version of the problem would have acollection of paper markers, each labeled with its value in dollarsand its weight in grams, and a knapsack drawn on a sheet of paper.To make the paper version properly represent the problem, theknapsack should be an array of N cells and each gem sized to coverthe number of cells equal in number as its weight in carats. For example, if a gem weighs 2 carats, then its representation inthe knapsack is to occupy 2 cells of the knapsack array.

Explanation / Answer

This is a case of Greedy algorithm For example, there might be 7 gems, representedas pairs with weight, value: ruby (2 carats, $100); diamond (1carat, $400); emerald (3 carats, $250); amethyst (2 carats, $50);opal (1 carat, $300); sapphire (2 carats, $500); malachite (1carat, $60). The seven gems total 12 carats, but the thief can onlycarry 5. Which stones should she take to get the maximum value indollars? First calculate the value per carat for every gem. (dividevalue of gem by number of carats of the gem) This gives, ruby - $50 per carat , diamond $400 per carat ,emerald $250/3 per carat , amethyst $25 per carat, opal $300 per carat, sapphire $250 per carat , malachite $60 percarat Now sort them according to the value percarat: diamond $400 per carat , opal $300 per carat, sapphire $250 per carat , emerald $250/3 per carat , malachite $60 per carat ruby $50 per carat amethyst $25 per carat, Now select from the maximum number of carats out of caratsavailable in the descending order of value per carat 1) select diamond -- 1 carat available..... remaining knapsackability 4carats 2) select opal -----1 carat available..... remaining knapsackability 3carats 3) select sapphire ----2 carats available..... remaining knapsackability 1carat 4) select emerald---- gem is of 3carats but availableknapsackability is 1 carat..tso he cannot take the emerald gem 5) select malachite---gem is of 1 carat...avaialble knapsackability is also 1 carat..so take malachite..after this remainingknapsack ability is 0 Now value the theif got is :diamond + opal + sapphire +malachite                                       = $ ( 400 + 300 + 500 + 60 )                                       = $ 1260

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.