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_inline67426 is either a zero or a one, there are tex2html_wrap_inline60061 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_inline67440 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_inline67442 which is called the objective function .

Since there are tex2html_wrap_inline60061 possible values of X the running time of a brute-force solution is tex2html_wrap_inline59959. 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_inline67454.


next up previous contents index

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