Sorry about the strange way of writing the question. Yes, it is a Knapsack problem.
You got a list of item. Like you have a pirate ship, and you have a lot of different cannons that you can outfit the ship with. The different weapons deal different amount of damage. You have a weight constraint, or the ship will sink. You cannot use more cannons than the number of "weapon slots" you have. (Determined at runtime by choice of ship.) I want to know what combinations of cannons that does the most damage, when you can use x number of cannons, and the combined weight is not more than the max limit. The order of the cannons makes no difference at all. So in this situation I would have: Index Cannon name Cannon weight Cannon damage Number of "inner loops" in a "brute force" solution is determined by the number of slots, set at runtime. Total weight has a variable for the max weight for a valid solution. You want to find max cannon damage. On Oct 7, 12:06 pm, Theraot <[email protected]> wrote: > I have trouble undestranding the statement... > > If I got it well, you need to find a combination of items. > Where each item has a value defined by a kind of item. > There are a finite number of kinds of items each one with a value and > a number of times it can be used. > Also each item has a cost, and total of the cost must be below a > certain limit. > Now you want the combination that sums the maximum posible value. > > Is it? > > I think it's a knapsack problem (http://en.wikipedia.org/wiki/ > Knapsack_problem) > Very similar to the Change-making problem (http://en.wikipedia.org/ > wiki/Change-making_problem) > > Check those and see if they fit your situation. Also... could you > raname "Property1", "Property2", "intMinP1" and "intMaxP2" to > something more meaningful? It just helps getting me confused. > > Now, I think you could implement an genetic algorithm (http:// > en.wikipedia.org/wiki/Genetic_algorithm) for this, but that's not a > deterministic solution. If you want a deterministic solution we will > need to analyse the problem futher. > > If the order doesn't matter in the combination (I forgot the in math > terminology for that :P), then don't store any order, it will be > easier to store how many of each posible kind of elements you take. > > My bet on optimizing this would be sorting the kinds of itmes by > eficiency = value / cost, and try first those with higher eficiency > until you can't take more, then the next with more eficiency. If the > order doesn't matter, you can go right to the number of item you want > by dividing the maximun cost by the the cost of the kind of item, > round and multiply by the cost again. > > May be I got I wrong, but I hope that helps. > > Theraot > > On 5 oct, 12:01, Ronny <[email protected]> wrote: > > > > > Hey guys, > > I’m a “basic”/hobby VB.NET user who is trying to create some code that > > I think might be very complex. So I was hoping someone could help me > > understand how this might be done. And it might be mostly a > > mathematical question. > > > I want to find an optimal solution of combinations of a quite large > > data set, based on a few parameters. > > > So I have a class with a few members in it. > > Index as Integer ‘Just a counting index > > Name as String ‘Name of the item > > Value as Integer ‘The value I want the sum to be as high as > > possible > > Limit as Integer ‘The number of times this item can show > > in one solution > > Property1 as Integer ‘Property where item is excluded if less > > than intMinP1 > > Property2 as Integer ‘Property where the sum cannot be more than > > intMaxP2 > > > I have a “collection” class (if that’s the name) with an array/list of > > the first class. > > There is about 250 items in this list. (But since most items can be > > used multiple times (limited by ‘Limit’), the total number of items to > > try is a lot bigger.) > > > I have a few variables. > > intAvailable as Integer ‘Number of items in solution – Can be 1 to > > 12 > > intMinP1 as Integer ‘Minimum value of any Property1 in > > solution > > intMaxP2 as Integer ‘Maximum value of the sum of Property2 in > > solution > > > I want to know what combination of items from my list that gives the > > highest Value. But none of the items can have a Property1 value less > > than intMinP1. And the total sum of Property2 cannot be more than > > intMaxP2. The same item from the collection can be in the solution > > multiple times, but limited by the Limit property. > > > The optimal solution (highest value) might be that you only use 9 > > items, even if intAvailable is 10. > > > My first thought is that you would need to loop through all > > combinations. But with 250 items, many of them can be used multiple > > times in the same solution. So you might have like 2,500 items and up > > to 12 item combinations in your solution. 2,500^12 is a lot of > > combinations. I know a processor can be fast with mathematical > > calculations, but this sounds like an “over the night” calculation, > > and not a “let’s try this, wait a minute, change some of the variables > > and let’s try this way”. > > > So, if I want to do “brute force” and loop through all combinations, > > how can I do that? > > > Also, if I want some “smart” solution, how can I do that? I’m sure > > there are programs that do those calculations, and at super speed.. So > > there must be solutions for it? > > > Some thoughts I had: > > Some smart selection that excludes any options already tried (but in a > > different sequence)? > > You have 2 items in your solution. If you try Item A and Item B, then > > you also know Item B and Item A. > > 3 items, you try Item A, Item A and Item B you also know A, B, A, and > > B, A, A etc. etc. > > > Some smarter algorithm that figures out if your result is getting > > worse, then don’t continue with this path, you won’t find a better > > solution here, and start on a different path? > > > Limit the selections? > > If you can use 10 items, don’t try combinations with only 2 or 3 > > items. Cut it off somewhere at like 7 to 10 items. You greatly reduced > > your combinations, but you could theoretically exclude the optimal > > solution. > > > If anyone can help me understand how this is done, I would be very > > happy. > > > Thanks, > > Ronny
