Genetic Algorithm-Knapsack Problem
It is often the case that we must make the best choices that we can within a limited budget, consider -- grocery shopping while staying within your budget; packing a suitcase for a trip while staying below your luggage weight allowance; deciding which items you will carry in a small handbag; deciding which programs and documents you will keep on your computer with a finite hard drive capacity; deciding which topics to study for an exam with the time and mental energy available!
There are also many examples of this decision problem in commercial and industrial scenarios -- a manufacturing plant choosing what to produce with a limited number of operational hours; forming a sports team line-up with some maximum budget for players; filling a shipping vessel with the most profitable contents while limited by the maximum weight and volume of the cargo hold; which towns a salesman will visit with a limited marketing budget.
This puzzle has a mathematical name - it is called the Knapsack Problem. It is named because the decision problem is imagined as filling a knapsack (or rucksack, backpack etc.) with the best choice of items. However the difficulty is that the total weight of the chosen items must not exceed the maximum weight capacity of the knapsack (single constraint). The problem can also be extended to two constraints - where the knapsack has a defined maximum weight capacity and a maximum volume capacity. The more constraints that are added, the more difficult it becomes to find the optimal solution to the problem. In fact this problem is considered to be NP-Hard - the time required to find a perfect solution grows exponentially with the number of items!
Sometimes it is simple to visualise the decision (Grocery Shopping : monetary cost of an item vs a budget) or a little more abstract (Manufacturing: hours spent on a job vs the total operational hours of a plant) -- notice that the choice can be a set of items or a series of actions. Any decision can be considered in this way if the task is to choose some, but not all, of a set of possibilities.
A particular variation of this problem is called the 0-1 Knapsack Problem. In this case we would like to maximise the total profit by examining each and every item from a set, and decide whether to take or leave that item (but we cannot take more than one of each item). We also must remember to abide by the constraint that the total weight of our chosen items is less than or equal to our maximum weight capacity.
The constraints of these problems can be defined by the Capacity Ratio - this is ratio of maximum capacity to the total weight of all available items. In other words, a Capacity Ratio of 1 would mean that you have space for all of the available items. Capacity Ratio of 0.5 means that your knapsack will hold only half of the available total weight. Capacity Ratio of 0.1 results in a knapsack that holds only 10% of the available item weight. Note that the item weights and values are all different - 10% of the available total item weight does not necessarily mean 10% of the total number of available items.