Question

Thief enters into the bank for robbery carrying a bag with 20KG capacity. He sees only...

Thief enters into the bank for robbery carrying a bag with 20KG capacity. He sees only 5 items with the following weights and values. In which order thief should pick items if he can take the fraction of any the items so that maximum gain can be achieved?

Items

1

2

3

4

5

6

7

Weight

3

17

7

6

15

5

10

Value

1

4

1

7

5

3

2

Homework Answers

Answer #1

Here, fractional knapsack algorithm has to be performed on the given data.

The given data is :

Item 1 2 3 4 5 6 7
Weight 3 17 7 6 15 5 10
Value 1 4 1 7 5 3 2

Capacity given is 20 Kg.

The fractional knapsack algorithm is implemented using the following steps :

Step 1 :

Find the value / weight ratio of each item.

Let r = value / weight.

Then,

Item 1 2 3 4 5 6 7
Weight 3 17 7 6 15 5 10
Value 1 4 1 7 5 3 2
r 0.334 0.235 0.143 1.167 0.334 0.6 0.2

Step 2 :

Sort the items in non-increasing order of r value.

Item 4 6 1 5 2 7 3
Weight 6 5 3 15 17 10 7
Value 7 3 1 5 4 2 1
r 1.167 0.6 0.334 0.334 0.235 0.2 0.143

Initialize net value = 0

Step 3 :

Select the first item from the sorted list whose weight is less than or equal to the given capacity.

The item selected is Item 4.

Its weight is 6 Kg.

Its value is 7.

So, net value till now = old net value + value of item = 0 + 7 = 7 and the new capacity = Old capacity - weight of item = 20 Kg - 6 Kg = 14 Kg.

Step 4 :

Select the next item from the sorted list whose weight is less than or equal to the updated capacity.

The item selected is Item 6.

Its weight is 5 Kg.

Its value is 3.

So, net value till now = old net value + value of item = 7 + 3 = 10 and the new capacity = Old capacity - weight of item = 14 Kg - 5 Kg = 9 Kg.

Step 5 :

Select the next item from the sorted list whose weight is less than or equal to the updated capacity.

The item selected is Item 1.

Its weight is 3 Kg.

Its value is 1.

So, net value till now = old net value + value of item = 10 + 1 = 11 and the new capacity = Old capacity - weight of item = 9 Kg - 3 Kg = 6 Kg.

Step 6 :

Select the next item from the sorted list whose weight is less than or equal to the updated capacity.

Item 5 cannot be chosen as its weight exceeds the updated capacity.

But since fractional knapsack has to be used, a fraction of item 5 can be used.

Updated capacity = 6 Kg

15 kg of item 5 has value of 5.

Then, 6 kg of item 5 has value = ( 5 / 15 ) * 6 = 2.

So, net value till now = old net value + value of item = 11 + 2 = 13 and the new capacity = Old capacity - weight of item = 6 Kg - 6 Kg = 0 Kg.

The capacity is now 0 kg.

The required items are selected in the order :

Item 4, Item 6, Item 1, Item 5 of 6 kg.

Hence, the answer is :

Item 4, Item 6, Item 1, Item 5 of 6 kg.

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
1)A student enters a multiple-choice exam. Each question has 4 choices however, only 1 of the...
1)A student enters a multiple-choice exam. Each question has 4 choices however, only 1 of the questions is correct. The probability that the student knows the answer to any given question is equal to the sum of the first 3 values in your dataset (my dataset is below) [4 5 5 2 4 4 6 3 3 7 5 3 6 3 4 4 6 5 4 5 3 7 5 5 4 2 6 5 6 6] divided by...
Barry is currently obese and would like to lose weight. Barry is watching television and sees...
Barry is currently obese and would like to lose weight. Barry is watching television and sees two different infomercials about weight loss products. The first infomercial is for a weight loss "supplement, called ICBINM (I Can't Believe It's Not Meth), the customer takes daily to "increase metabolism and energy". The infomercial for ICBINM shows 3 different verified customers who used the product and lost a lot of weight. The second infomercial is for a weight loss "program", called TNKD (The...
Kuya conducted a taste-test study of tofu. He gathered 20 of his friends and took them...
Kuya conducted a taste-test study of tofu. He gathered 20 of his friends and took them to various tofu dinners on three Sundays. Firstly, a Chinese tofu dinner. He then asked his friends to rate how much they enjoyed the tofu (from 1 to 10 with 1 = hate it, and 10 = love it). The following Sunday, they went for a Thai tofu dinner and collected their ratings. On the third Sunday, he took these (lucky?) friends to a...
Wandering through Wal-Mart one night, you come across a delightful looking bag (the Hershey's Super Mix...
Wandering through Wal-Mart one night, you come across a delightful looking bag (the Hershey's Super Mix Assorted Candy 32.9 oz, 70 ct. ) of candy which included three of your favorites – Heath Bar, Kit-Kat and Reese’s. Upon ripping open the bag later, you were dismayed to find few pieces of your favorites and almost 50% of the bag consisting of Milk Duds (appropriately named methinks!). When drifting off into Glucose Stuporland later that night on the couch, you dreamt...
1. A man has a loan of 50,000 in a bank that gives 12% simple interest....
1. A man has a loan of 50,000 in a bank that gives 12% simple interest. How much is the interest if he plans to pay after 5 years? 2. A man can save 10,000 per month for 2years, If the bank offers 5% compounded monthly, what is n? 3. A man has a loan of 50,000 in a bank that gives an interest rate of 12% compounded quarterly? If he plans to pay after 6months, how much is the...
The game requires $5 to play, once the player is admitted, he or she has the...
The game requires $5 to play, once the player is admitted, he or she has the opportunity to take a chance with luck and pick from the bag. If the player receives a M&M, the player loses. If the player wins a Reese’s Pieces candy, the player wins. If the player wins they may roll a dice for a second turn, if the die rolls on a even number, they may pick from the bag once again with no extra...
Fremont Computer Company has been purchasing carrying cases for its portable computers at a purchase price...
Fremont Computer Company has been purchasing carrying cases for its portable computers at a purchase price of $111 per unit. The company, which is currently operating below full capacity, charges factory overhead to production at the rate of 50% of direct labor cost. The unit costs to produce comparable carrying cases are expected to be as follows: Direct materials $55 Direct labor 40 Factory overhead (50% of direct labor) 20 Total cost per unit $115 If Fremont Computer Company manufactures...
1. If we increase our food intake, we generally gain weight. Nutrition scientists can calculate the...
1. If we increase our food intake, we generally gain weight. Nutrition scientists can calculate the amount of weight gain that would be associated with a given increase in calories. In one study, 16 nonobese adults, aged 25 to 36 years, were fed 1000 calories per day in excess of the calories needed to maintain a stable body weight. The subjects maintained this diet for eight weeks, so they consumed a total of 56,000 extra calories. According to theory, 3500...
Jon Snow is preparing his army to face the white walkers. He wants his archers to...
Jon Snow is preparing his army to face the white walkers. He wants his archers to be equipped with the best quality arrowheads. His blacksmith will work around the clock with a team of experienced crafters to meet his orders. Jon has asked that each hour, 20 randomly selected arrowheads to be delivered to him so that he can personally check on the quality. The results for 20 hours of sampling are provided below. Sample Defectives 1 3 2 3...
Fremont Computer Company has been purchasing carrying cases for its portable computers at a purchase price...
Fremont Computer Company has been purchasing carrying cases for its portable computers at a purchase price of $89 per unit. The company, which is currently operating below full capacity, charges factory overhead to production at the rate of 60% of direct labor cost. The unit costs to produce comparable carrying cases are expected to be as follows: Direct materials $59 Direct labor 20 Factory overhead (60% of direct labor) 12 Total cost per unit $91 If Fremont Computer Company manufactures...