You are going to the 2018 Geography conference in New Orleans, your carry-on bag

Question

You are going to the 2018 Geography conference in New Orleans, your carry-on bag is limited to 20 pounds, the rest you will have to but in a checked bag. Of the items listed in the table below which can you take in your carry-on bag? Solve using the greedy algorithm and with LINGO.

Item

Weight

Value

Business Cards

2

3

Toiletries

3

4

Notebook and pens

4

5

Laptop and charger

5

8

Clothes and Shoes

9

10

1. Solve using Greedy Algorithm (show solution below)

2. Solve using LINGO (show code and solution below).

3. Are the answers different? If so why?

Item

Weight

Value

Business Cards

2

3

Toiletries

3

4

Notebook and pens

4

5

Laptop and charger

5

8

Clothes and Shoes

9

10

Explanation / Answer

1) In greedy algo we choose max weight first thn second max and so on .

1st Max weight = cloth and shoes of 9 pound s

Thn 2nd max = Laptop carrer of 5 pounds

Now total weight 14 pound

Thn 3rd max = notebook and pen of 4 pounds

Now total weight is 18 , only 2 pound remaining . If we select next max the weight becomes 21 pound that will exceed limit so we select business cards of 2 pound.

So as per the greedy algo bag consist of above item.

2)LINGO CODE :

Weight <= 20

Min = 2

Max = 9

MinValue =3

MaxValue =10

LINGO algo solve the above problem efficiently by considering both value and weight.

3) yes Answer will be different because in gready algo pick up item based only on their weight by taking max weight first and least weight in last.

Where as in LINGO problem wipo be solve efficiently and provide optimzed output . It considered both weight and value both and get the optimzed output.

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

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