Đang chuẩn bị liên kết để tải về tài liệu:
Realization of knapsack problem solving algorithm and some of its applications

A realization of one algorithm for solving the classical knapsack problem which is much faster than the dynamical programming method and requires less memory is suggested. The popular situation in the Big Brother TV show is used to exemplify its applicability. For the purpose, the number of the wishes of all players are maximized. | Yugoslav Journal of Operations Research Vol 19 (2009), Number 1, 113-122 DOI:10.2298/YUJOR0901113I REALIZATION OF KNAPSACK PROBLEM SOLVING ALGORITHM AND SOME OF ITS APPLICATIONS Dimiter IVANCHEV New Bulgarian University, Sofia divanchev@nbu.bg Elena RADOVANOVA Technical University of Sofia ear@abv.bg Received: December 2007 / Accepted: May 2009 Abstract: A realization of one algorithm for solving the classical knapsack problem which is much faster than the dynamical programming method and requires less memory is suggested. The popular situation in the Big Brother TV show is used to exemplify its applicability. For the purpose, the number of the wishes of all players are maximized. Keywords: Knapsack problem, algorithmic realization, optimum budget, network optimization. 1. INTRODUCTION AND MOTIVATION The following situation is frequently observed. A group of persons try to arrange a budget (some quantity of money) for a future period – a week, a month, a year etc. Sometimes the interests of the persons are contradictable, which implies a different behavior of the players. Due to the large number of combinations a person of the group can be more or less satisfied. A typical example of this situation is the Big Brother TV show. The players frequently have to arrange their budget for the next week. As a rule, they quarrel and feel dissatisfied. Further, the above situation is taken as an example and some variants of the budget arrangement are suggested in order to maximize the number of wishes satisfied or to be sounder and fairer. 114 D. Ivanchev, E. Radovanova / Realization of Knapsack 2. PROBLEM STATEMENT AND THE MODEL Let us now consider the situation mentioned above and let us introduce the following notations: K - the amount of money (currency), i.e. EUR we can use next week, m - the number of all the players in the show. n - the number of the products (items) they can order, k j - the price of the j − th item they can order and by, j =1,2,., .