TAILIEUCHUNG - 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: REALIZATION OF KNAPSACK PROBLEM SOLVING ALGORITHM AND SOME OF ITS APPLICATIONS Dimiter IVANCHEV New Bulgarian University, Sofia divanchev@ Elena RADOVANOVA Technical University of Sofia ear@ 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), . 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,., .

• Toán học
• Knapsack problem
• Algorithmic realization
• Optimum budget
• Network optimization
• Dynamical programming method
• An OR practitioner’s solution approach
• The multidimensional knapsack problem
• Robust population based metaheuristic
• Multidimensional Knapsack Problem
• Solve industrial size problems
• Advanced Algorithms Analysis and Design
• Lecture Advanced Algorithms Analysis and Design
• Bài giảng Phân tích và thiết kế thuật toán nâng cao
• 0 1 knapsack problem
• Dynamic programming
• Developing algorithm for knapsack
• 0 1 knapsack problem’s algorithm
• Optimal weight triangulation
• Resource scheduling
• Non preemptive case
• Heuristic method
• Heuristic algorithm
• Greedy algorithms
• Activity selection problem
• Fractional knapsack problem
• Branch and bound technique
• The queens problem
• ALGORITHMS ANALYSIS
• Topological Sorting
• WEIGHTED GRAPHS
• Representation
• Algorithms unplugged
• Eulerian circuits
• Shortest paths
• Marriage broker
• The knapsack problem
• Simulated annealing
• Dynamic programing
• Knapsack shaking approach
• Longest common subsequence
• Parallel LCS
• Classical dynamic programming
• Automata technique
• Algorithm design
• Lecture Algorithm design
• Algorithm analysis
• Weighted interval scheduling
• Approximation Algorithms
• Vertex cover
• Khoa học máy tính
• Tạp chí khoa học
• Multi objective Evolutionary Algorithm
• Pareto Optimisation
• Hyper volume
• Lecture Design and Analysis of Algorithms
• Bài giảng Thiết kế và phân tích thuật toán
• Analysis of Algorithms
• Design of Algorithms