Re: optimization problem (Knapsack)

> I am not even sure where to look for suggestions

Sounds like Knapsack problem and family ... but I'm not sure about your side conditions.

edit

ah sounds good:

Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

So pick a negative value of -1 or negative number representing the precision.

You'll find plenty of implementations

update

... though be aware that it's NP hard, runtime will depend on how good your result has to be and if you need a guarantied optimal solution.

Cheers Rolf
_{(addicted to the Perl Programming Language :)

Wikisyntax for the Monastery}

Comment on Re: optimization problem (Knapsack)

Replies are listed 'Best First'.
Re^2: optimization problem (Knapsack) by spencoid (Acolyte) on Jun 10, 2018 at 23:34 UTC
Thanks for the hints. I does seem like a type of napsack problem or a change problem however there are smoe specifics that make it a little more complex, maybe. Also I did some fiddling with the script to try to see what strategy I owould use as a human and try to determine if I could use that as a basis from which to develop code. The weights do (sort of) have two attributes, weight and precision. Precision could probably be equated with value but I really can not wrap my head around this one :) The weight examples I gave were not representative of the true problem. The weights do run from smallest to largest and the values are 5 or 6 decimal places. A strategy I used fairly well to do it by hand is very simple but ... As in the example I found online of the coin change problem you can add the largest number of the largest number of weights and add that to the total as long as the total does not exceed the target value. Continue with lesser weights and finally add the number of the smallest weights. The smallest weight is quite small and there are a lot of intermediates so it might make sense to just keep it as simple as possible and not worry about the perfect solution. Once the weights are chosen by this method, it is never possible to substitute more larger weights for smaller ones, of course but as in the coin change problem it might be possible to get closer with more smaller weights if the remainder is then satisfied with fewer even smaller coins. I can very easily code the simplistic solution and fiddle around to see how much improvement might be possible. I might even get an idea as to how to test for a better solution once the simple method is used. I have not used much math in many years and could not follow most of the online examples. There was a python example for the syntax is so different from Perl or any language I have used that it would take me forever to figure out. I will search for Perl coin change problem and similar topics once my satellite internet connection improves after 2:00 AM but if anyone has links for examples of the coin change or napsack problems written in Perl that would be very much appreciated.	[reply]

Replies are listed 'Best First'.

Re^2: optimization problem (Knapsack)
by spencoid (Acolyte) on Jun 10, 2018 at 23:34 UTC

Thanks for the hints. I does seem like a type of napsack problem or a change problem however there are smoe specifics that make it a little more complex, maybe. Also I did some fiddling with the script to try to see what strategy I owould use as a human and try to determine if I could use that as a basis from which to develop code. The weights do (sort of) have two attributes, weight and precision. Precision could probably be equated with value but I really can not wrap my head around this one :) The weight examples I gave were not representative of the true problem. The weights do run from smallest to largest and the values are 5 or 6 decimal places. A strategy I used fairly well to do it by hand is very simple but ... As in the example I found online of the coin change problem you can add the largest number of the largest number of weights and add that to the total as long as the total does not exceed the target value. Continue with lesser weights and finally add the number of the smallest weights. The smallest weight is quite small and there are a lot of intermediates so it might make sense to just keep it as simple as possible and not worry about the perfect solution. Once the weights are chosen by this method, it is never possible to substitute more larger weights for smaller ones, of course but as in the coin change problem it might be possible to get closer with more smaller weights if the remainder is then satisfied with fewer even smaller coins. I can very easily code the simplistic solution and fiddle around to see how much improvement might be possible. I might even get an idea as to how to test for a better solution once the simple method is used. I have not used much math in many years and could not follow most of the online examples. There was a python example for the syntax is so different from Perl or any language I have used that it would take me forever to figure out. I will search for Perl coin change problem and similar topics once my satellite internet connection improves after 2:00 AM but if anyone has links for examples of the coin change or napsack problems written in Perl that would be very much appreciated.

[reply]