Abstract:
We consider a particular case of the knapsack problem when the weights of all items are the same and the costs of items take two different values. By a strategy of the solution of the knapsack problem by the branch and bound method we mean the method of selecting of the next subtask from the list of subtasks considered in the solution process in conjunction with the method of selecting of the variable to decompose the selected subtask if it is necessary to perform this decomposition. For the considered particular case of the knapsack problem the optimal strategy of this case solution by the branch and bound method is found.
Key words:the knapsack problem, the branch and bound method, the complexity of a problem solution, the strategy of a solution.
Fulltext:
PDF file (406 kB)