Solution Found!
The garage sale problem (courtesy of Professor Lofti Zadeh). On a given Sunday morning
Chapter 6, Problem 6.16(choose chapter or problem)
The garage sale problem (courtesy of Professor Lofti Zadeh). On a given Sunday morning, thereare n garage sales going on, g1, g2, . . . , gn. For each garage sale gj , you have an estimate of itsvalue to you, vj . For any two garage sales you have an estimate of the transportation cost dijof getting from gi to gj . You are also given the costs d0j and dj0 of going between your homeand each garage sale. You want to find a tour of a subset of the given garage sales, starting andending at home, that maximizes your total benefit minus your total transportation costs.Give an algorithm that solves this problem in time O(n22n). (Hint: This is closely related to thetraveling salesman problem.)
Questions & Answers
QUESTION:
The garage sale problem (courtesy of Professor Lofti Zadeh). On a given Sunday morning, thereare n garage sales going on, g1, g2, . . . , gn. For each garage sale gj , you have an estimate of itsvalue to you, vj . For any two garage sales you have an estimate of the transportation cost dijof getting from gi to gj . You are also given the costs d0j and dj0 of going between your homeand each garage sale. You want to find a tour of a subset of the given garage sales, starting andending at home, that maximizes your total benefit minus your total transportation costs.Give an algorithm that solves this problem in time O(n22n). (Hint: This is closely related to thetraveling salesman problem.)
ANSWER:Step 1 of 3
There are n garage sales going on,
Given the costs 
