Consider the generalized knapsack problem studied in Exercise 4.47. Extend the formulation in Application 4.3 in order to transform this problem into a longest path problem in an acyclic network.
Exercise 4.47
Generalized knapsack problem. In the knapsack problem discussed in Application 4.3, suppose that each item j has three associated numbers: value Vj, weight Wj, and volume rj. We want to maximize the value of the items put in the knapsack subject to the condition that the total weight of the items is at most Wand the total volume is at most R. Formulate this problem as a shortest path problem with an additional constraint.