A small college has a budget 150000 for physical plant impro

A small college has a budget $150,000 for physical plant improvements over the summer. The posible projects have been rated according to their value (see the table below). Which should they do to maximize the total value within their budget? Use the branch-and-bound method to solve this knapsack type problem

Project

Cost

Value

1

30,000

8

2

45,000

9

3

60,000

10

4

40,000

7

5

50,000

8

Solution

This problem may be formulated and solved in a variety of ways. The method
proposed here is of interest in that it provides initially a solution which is ap-
proximately optimal and also an upper bound on the value of the optimal solu-
tion. Thus, computation may be terminated at any point where it is felt that
further improvements in the solution are not worth the additional computational
effort. The nature of the algorithm is such that the approximation tends to be
good for problems involving a large number of items where each item makes a
small contribution to the objective function and to the restriction. Further, it
appears that the efficiency of the algorithm increases as the size of the problem
increases. Nonetheless, as with other branch and bound [8] algorithms, the
memory and time requirements are quite large for problems involving many
items.

In this problem we have to maximize value , and plan the project cost within 150,000$

analytically we can say that project 1 has fairly high value and its has least costly

We can easily do 5 project1 within 150,000 $ , that will give a total value of 40.

We can try analysing other values but it wont give a value greater than 40 within budget of 150,000 $

so we will do 5 project1