Question: You, along with a group of your friends, are planning a camping trip during Spring Break. The group must hike several miles through the woods to get to the campsite and anything that is needed on this trip must be packed in a knapsack and carried to the campsite. You have identified eight different items you would like to take on the trip, but you know you can’t take them all since you don’t believe that you’ll be able to carry more than 35 pounds all the way to the campsite. Because of this, you have identified the usefulness of each item along with its weight and placed this information into the following table:

In addition, you’ve decided that since items 3 and 4 are similar, if you take one of these, you won’t take the other.

Formulate this as a 0-1 programming problem whose objective is to maximize the total usefulness of the items carried. Make sure to define the decision variables carefully, and then specify the objective function and the constraints in terms of them.