Logo Data Structures and Algorithms with Object-Oriented Design Patterns in C++
next up previous contents index

Brute-Force Algorithm

Since each of the elements of tex2html_wrap_inline68425 is either a zero or a one, there are tex2html_wrap_inline60823 possible values for X. A brute-force algorithm to solve this problem finds the best solution by enumerating all the possible values of X.

For each possible value of X we check first if the constraint tex2html_wrap_inline68439 is satisfied. A value which satisfies the constraint is called a feasible solution . The solution to the problem is the feasible solution which minimizes tex2html_wrap_inline68441 which is called the objective function .

Since there are tex2html_wrap_inline60823 possible values of X the running time of a brute-force solution is tex2html_wrap_inline60725. The running time needed to determine whether a possible value is a feasible solution is O(n) and the time required to evaluate the objective function is also O(n). Therefore, the running time of the brute-force algorithm is tex2html_wrap_inline68453.


next up previous contents index

Bruno Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.