Exploration of Greedy Algorithm Application in Knapsack Problem and Actual User Experience in Games

Abstract: In this paper, through analysis of 01 knapsack problem and greedy algorithm and rough application of greedy algorithm in 01 knapsack problem via C++ code (unable to solve), the mentality of players as well as how to apply it in the actual game were discussed.

Key words: greedy algorithm; 01 knapsack problem; game programming; game psychology.

Text part

1.Introduction

By definition, greedy algorithm is about making the best option for the moment for each step in the process of answering a question, which means obtaining the locally optimal solution in approximation. under many game situations, it is necessary to echo psychology of players to use greedy algorithm to solve problems. While 01 knapsack problem, as one of the most basic problem in dynamic planning, though it can not be solved with greedy algorithm, through analysis towards it, we could find better method to make a deeper use of greedy algorithm to solve game-related problems.

2. Main research contents

2.1Analysis of concept

2.1.1Greedy algorithm

Greedy algorithm, also known as greedy method, by definition, it is about making the best option for the moment for each step in the process of answering a question. The main thought is to make the best decision through every step, and try to get the globally optimal solution via such locally optimal solutions.

It is common in the aspect of playing cards, stock investment, entrance examination for voluntary reporting etc. in daily life.

In games, it is generally common in survival games and horror games, among these games, players’ knapsack may be different from that in other types of games, it will have a better simulation on real situation, and burdens will affect players’ survival ability. At such time, players need to make a choice, and greedy algorithm could be one of the means to make such choice.

2.1.2 01 knapsack problem

In plain speaking, 01 knapsack problem means how to put n articles in different values and weights into a knapsack under the weight of m to realize maximum earnings. There is one and only one for each kind of article with the option of putting or not putting, therefore, 01 knapsack is also one of the simplest knapsack problems.

Generally speaking, knapsack problem may be simplified to a great extent in games, even in survival and horror games partial to simulation of reality, generally conditions like safe storage of articles, articles damage and even decimal knapsack may not be taken into account. hence, using 01 knapsack problem model could simulate the conditions of knapsack mechanism in most games.

2.2 Code analysis

In this programming, the code editor used was Visual Studio and the code language used was C++.  

2.2.1 Display of operation interface

Figure 1 Operation Interface

2.2.2 Code analysis

1.Knapsack construction

Users may construct knapsack via inputting.

First of all, users should be guided to transfer the volume data they input into the array, to construct a knapsack that is of the same number of the input data by users in size (in quantity), and then, users should be guided to input the price by order. In case that the number of input price is different with the number of input volume, the system will skip to reenter the price.

Figure 2 Knapsack Construction Correlation Function

2.Ranking by earnings

As regard to use of greedy algorithm, I chose to use greedy algorithm for article earnings (i.e. unit price), therefore, first of all, I calculated the article earnings by unit price, and then ranked all articles with selection ranking by the unit price.

Figure 3 Selection of Ranking Functions

3.Use simple greedy algorithm to get the final result

Figure 4 Greedy Algorithm Related Code

4.Analysis of player experience in game psychology

First of all, for example, in a horror survival game, players need to pick supplies to insure survival while hiding from monsters, every time when the players go to pick props, there will be different kinds of props with different values and weights, at this moment, high-end players might choose in virtue of their understanding and experience in the game, however, for casual games with larger audience, or the gamers that could get the largest sense of fear in their first experience, excessive difficulty might lead to much less satisfaction than boredom for games, undoubtedly, such a game is defective.

Figure 5 Narrow Knapsacks in Classic Horror Survival Game Resident Evil

Greedy algorithm might be worthy of reference in how to give players positive feedback in knapsack and articles picking

3. Conclusion

After programming and research, it is not hard to see the advantages of greedy algorithm lie in its simple algorithm as well as low time and space complexity. But the shortcoming is that the exact globally optimal solution may not be insured when each independent choice is mutually affected.

In the simple game knapsack model derived from 01 knapsack problem, it could absolutely satisfy players’ demand, i.e. choose the best option when picking props every time, so as to make players get timely feedback on satisfaction.

The game producer could set two degrees of difficulty in the game design, in the high difficulty, there is no assistance to enable high-end player to gamble in their minds, while in the other low difficulty, the game producer may use the thought o greedy algorithm to set auxiliary mechanism, so that those causal games concern the actual game experience instead of the final global optimal solution could automatically choose articles by a certain demand (such as full degree, weight, selling price) when picking the props every time, and those players will be provided with more time to experience in the core game mechanism, thus to improve their experience and make them more comfortable.

Bibliography ：

[1] Preparation of “China Science Communication” science encyclopedia entry and application of work program. Baidu Baike Greedy Algorithm [EB/OL].https://baike.baidu.com/item/%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95/5411800?fr=aladdin#6,.

[2] Summary of sorting algorithm [EB/OL].https://www.runoob.com/w3cnote/sort-algorithm-summary.html,.

[3]. Learn and progress with an open mind. Greedy algorithm – partial knapsack problem [EB/OL]. https://www.runoob.com/w3cnote/sort-algorithm-summary.html,. (The paper is prepared for the author to solve partial knapsack problem, the learning idea is without reference to code.)