For each problem listed below, state if it is NP complete. If it is NP complete, explain which NP complete it is most similar to. If it is not NP completed, either explain the similarity to another problem or explain how to solve it.

-Find an ice cream truck route that drives every road exactly twice, once in each direction. (U-turns at intersection are permitted.)

-Find the quickest fire truck route from the fire station to the fire site.

-Select a set of intersection on which to place mail boxes so that nobody lives more than one block away from a mail box. Find the smallest set possible.

-Plan an order for a politicians speaking engagement that has the least possible total driving distance

-At the 10 pounds for a dollar book sale, select as many books as possible without exceeding the weight limit. (Think carefully about this one.)

-A thief is robbing the Each Item cost one dollar store. The thief has a knapsack that can hold at most 50 pounds worth of items. The thief wants to select a set of items with maximal value but whose total weight does not exceed 50 pounds.

-In order to support intra-state commerce, the state has agreed to plow a subset of roads that allow reaching any city center from any other city center in state. Find the cheapest subset of roads that satisfy this agreement.

-You are at Toys-R Us trying to select a set of present to satisfy a greedy child. You have a long list of requested presents, each marked from 1 to 10 on a desirability scale. You must get at least 50 desirability points worth of presents, and you also must minimize cost.

-You have found someone in Portland who will sell you an Oculus Rift and also someone in Augusta. You decided to buy both. You wish to find the fastest way to drive to these two locations and return to your starting point.

-You wish to assign team members to a set of sports teams such that the sum of the rankings of the players on each team are close to equal as possible.