Multidimensional Knapsack problem is a NP-hard problem. The problem has been studied extensively in the literature. In this paper we provides a solution to a capital budgeting problem of Federal Government Budget in Nigeria using Hybrid Genetic Algorithms proposed by [32].We use also used the approach of [33] to model federal government budget by dividing the capital project into four groups which includes : The Economic sector (x1) , The Social Service sector (x2), The Environmental/Regional Development sector (x3), and The Administration sector (x4). Using MATLAB software for the analysis, it was observed that the optimal solution was optimal solution value is 277.64 billion naira. The result shows that the first and the second sector will be selected (x1, x2 = 1;x3, x4 = 0).