Distance traveled (not traveling sales man)
in [Java Programming]
|
From: anal_aviator on 4 Apr 2010 19:15 On Sun, 4 Apr 2010 20:16:41 +0800, Eric Sosman wrote (in article <hp9vvc$pgh$1(a)news.eternal-september.org>): > On 4/4/2010 4:43 AM, anal_aviator wrote: >> Hi, >> >> I have a set number of distances (say 100) >> >> They range between 1 and 50 miles, if my target is 100 miles and i need >> to arrange them into groups what is the best way. >> >> I.E >> 25,38,36 >> 25,23,26,15,11 >> 25,23,36,15 >> 23,26,24,27 >> >> I could do a mix and mach for each distance against each other, but as the >> data set grows it is going to get silly, and if possible I want to keep each >> set to about the same size as the others. I.E 3-5 entries. >> >> Or if someone could give me the name for the branch of maths that would >> handle this, i can research that. > > It's not entirely clear what you're trying to do, but it > might (*might*) be what's known as the "bin packing problem." > GIYF. > > Thanks, "bin packing" appears to be the area that matches this data set., now i have a target i can start looking at it in more detail.
From: Lew on 4 Apr 2010 20:18 Jeff Higgins wrote: > Gee whiz, no code review? I'm devastated. :) Oh, c'mon, you know your code is good! But since you ask: > import java.util.ArrayList; > import java.util.List; > > public class Scratch { Personally I prefer to put the opening brace on its own line indented to the method signature, but your way is The Standard. > public static void main(String[] args) { Personally I prefer to put more white space in, such as inside method parentheses, but that's just a personal style matter and no reflection on your code. > int[] data = new int[100]; > for (int i = 0; i < 100; i++) { > data[i] = 1 + (int)(Math.random() * 50); } Now putting the closing brace there does violate The Standard, and mars readability. > List<List<Integer>> bins = > new ArrayList<List<Integer>>(); > int count = 0; > List<Integer> currentBin; Excellent variable name choices. > while ( count < 100 ) { > double sub = 0; I prefer to use double constants to initialize double variables. > currentBin = new ArrayList<Integer>(); > bins.add(currentBin); A blank line here could aid readability. > while (sub <= 100 && count < 100) { > if (sub + data[count] <= 100) { > sub += data[count]; > currentBin.add(data[count]); > count++; > } else break; Oooh, I don't like the lack of braces around the 'else' statement, nor the way you conflated all those lines into one. The code would be more maintainable if you followed The Standard on these. > } > } > for (List<Integer> l : bins) { 'l' is a very unfortunate choice for a variable name. > System.out.println(l.toString()); > } > } > } Nice clean algorithm. -- Lew
From: Jeff Higgins on 4 Apr 2010 20:42 On 4/4/2010 8:18 PM, Lew wrote: > Jeff Higgins wrote: >> Thanks! :) Here's a possible scenario: I want to assemble a set of weekend getaway itineraries. Each itinerary will consist of no less than three, and no more than five destinations. Destinations will be separated by no less than one kilometer, nor more than 50 kilometers in travel distance. The total travel distance for each itinerary must be no less than 10 kilometers, and no more than 120 kilometers. I am not concerned with the distance to the starting destination, nor the distance from the ending destination. For my input data, I have a list of ten thousand interesting destinations and their geographic coordinates from a region encompassing sixty five thousand square kilometers. The destinations are somewhat clumped around 30 cities, but are otherwise normally distributed. I hope to get as many itineraries as possible from this data. I'd be interested in hearing opinions on how to code a solution for this scenario, and would be happy to answer any questions concerning the proposed scenario.
From: Jeff Higgins on 4 Apr 2010 20:51 On 4/4/2010 8:42 PM, Jeff Higgins wrote: > On 4/4/2010 8:18 PM, Lew wrote: >> Jeff Higgins wrote: >>> > Thanks! :) > > ... For my input data, I have a list of ten thousand > interesting destinations and their geographic coordinates from a region > encompassing sixty five thousand square kilometers. The destinations > are somewhat clumped around 30 cities, but are otherwise normally > distributed. Oops. I can compute travel distances between any two destinations.
From: Lew on 5 Apr 2010 09:27
anal_aviator wrote: > The fact that the system is "unbound" is WHY it is interesting, since this > demonstration always had to produce a reasonable solution without running > forever. > You misconstrue. I didn't say the system was unbound, I said the solution space was unbound because the problem was not stated. This has nothing whatsoever to do with how long the program runs, but with how you know if you have a solution to the problem, let alone a correct solution. You didn't define "best" and you didn't define what constitutes membership in a "group". How can we help you if we don't know what you want? -- Lew |