# Knapsacks?

This topic is 4103 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi Really don't know how to put this simple but I give it a try. In my line of profession there exist a problem that very much resembles a knapsack problem that today are solved either manually or with some quite expensive tools that make static analysis of the problem. The knapsacks are equal in size. The gadgets to put in the knapsacks has a bunch of different properties such as size, priority and so on. In the end you want to minimize the number of sacks (almost true in this case) but still bring ALL the gadgets along. It is also nice to group gadgets by priority and other parameters. Just recently I figured that it might be possible use AI (or more specific GA) to solve this problem. What I look for here is any ideas/ suggestions around this quite vauge problem. Is GA suitable for solving a knapsacklike problem? Has it been done before? I appriciate any input. // Thanks // Javelin

##### Share on other sites
Genetic algorithms are suitable for almost any problem. Are they optimal... well, almost never. ;)

It would be very easy to develop a reasonable GA for this problem. First, devise a way of rating the fitness a candidate solution, eg. negative points for each sack used, positive points for grouping them, etc. Then work out how to implement the crossover and mutation operators, the former combining aspects of 2 solutions, the latter providing a modification on 1 solution. Then you're pretty much set.

However, the Wikipedia article indicates that there are other approaches, which I assume are more likely to be optimal, so I'd hesitate to recommend a GA approach if this is an important question.

##### Share on other sites
Grouping genetic algorithms are designed for exactly this sort of problem. They use specialized encodings and mutation operators to search the space of partitions of the items. They can be effective since once implemented it is easy to change around the objective function and constraints and they can find pretty good solutions for NP-hard problems.

1. 1
2. 2
3. 3
Rutin
23
4. 4
5. 5
khawk
14

• 9
• 11
• 11
• 23
• 12
• ### Forum Statistics

• Total Topics
633653
• Total Posts
3013164
×

## Important Information

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!