Weighted clustering algorithm I am looking to divide the 50 US states into n regions. The requirements in dividing are:


*

*Each state will be assigned a value

*The state values in each region should sum to make even group totals (as closely as possible). Which seems to make this a bin packing problem variation.

*The states in each region need to be geographically clustered, For example, CA+OR+WA should be clustered even though CA+GA+RI produces a smaller standard deviation of regional value totals.


This post asks a similar question. K-Means clustering seems overkill as states just need to be neighbors, however I am pretty green to stats.
As a side-note, I am ultimately looking to implement this in Ruby (which has a R library plugin).
UPDATE
The motivation behind the clustering is for ease of travel, therefore cluster compactness is more important than state adjacency (i.e. long, narrow, string-shaped clusters should be avoided). 
 A: You're really given a planar graph and you want to find connected components that have the smallest "spread" in values. While I don't know how to get an answer with provably guarantees, the following heuristic might work well. 
Assume all states have weights between 0 and $2^k$ say (for some $k$). Label all states with weights between 0 and $2^{k-1}-1$ as "0" and the rest as "1". Find the connected components of the graph with the same label. Now recurse in each component.
Essentially what you're doing is finding connected components such that in each component, the values don't vary "too much". If 2 is too coarse a granularity for you, you can choose some other factor between 1 and 2. 
The stopping point for the recursion is when the variance within a cluster thus formed is small enough. You'll end up with a hierarchical clustering in which the leaves are the desired clusters. 
A: This looks like a standard variation of bin packing problem with constraints to me.
https://en.wikipedia.org/wiki/Bin_packing_problem
It does not so much like clustering to me: the distances seems to be solely a constraint that only adjacent states must be selected. So none of the stuff you find under the term of "cluster analysis" will help you much. It's a constraint optimization that you are trying to do.
A: What about using Graph Partition (http://en.wikipedia.org/wiki/Graph_partition)? 
Where the graph here would be the USA, where the nodes are the states, the edges are the connections between states (i.e. there is an edge between two states if they are adjacent to each other). The subgraphs, or partitions would be the territories. You want to divide it into uniform components (equal revenue and maybe other constraints), so you would have some variation of uniform graph partition. 
