The new version of backtracking algorithm searching globally optimal solutions to discrete programming problems with Boolean variables is proposed. The paper contains an analytical search for the optimal parameters of the proposed algorithm and an experimental verification of the obtained results in relation to the knapsack problem. The experimentally obtained optimal numbers of variables simultaneously introduced into the basis or derived from it during each iteration of the proposed version of backtracking search as well as values of the gain in time when searching for a knapsack problem solution using this algorithm are in a good agreement with the analytical prediction. The independence of the optimal parameters of the proposed backtracking version from the characteristics of the computers used has also been experimentally confirmed.