Joel, Good taste in ISPs!
If you're willing to eat the difference when it guesses wrong on the approximation, the bucketizer might be ok... but you may have problems. It might do for a start. Try it and see how it's projections compare to what a real packer would achieve ... and how often it projects an impossible pack, and by how much. And if it misses UPS surcharges for odd shapes. If it's good enough, hey, it's easy. How right do you have to be? If your business model relies on this algorithm being 100% right, you've got other problems. ;-) > For such a small amount of data, I'd use brute force and try every > single variation. The reply above is probably correct, unless you have a large variety of box shapes and a large number of items per order because it's wholesale not retail. NP problems may expand exponentially, but if N is small enough, it doesn't get too large for modern computers. If you add some good heuristics, an approximate algorithm that gets a solution within 50% or 10% or 1% of the "correct" answer is frequently much faster (O(N) or O(NlogN) or at worst, O(P(N)); sometimes a monte-carlo approach or a random-walk/annealing/diffusion approach is good enough. I don't recomend coding the Knapsack / box-packing / bin-packing problem from first principles yourself, though, either as brute-force or approximate. Get pseudo code from a standard source (ACM Collected Algorithms, a computer science text, maybe a computer graphics or Knuth?). There are 7750 googles for Approximate Algorithm Bin-packing OR Knapsack OR Box-packing e.g., http://citeseer.ist.psu.edu/context/460103/0 so have fun! Note that in some trades, the percent of the box filled with product is low because you need PACKING for safety ... in which case, everything changes. The estimating of shipping charges was a specialized, value-added field before UPS put up their web service or whatever it is you're going to query. If you're retail, it's standard to just say "unless item has specified shipping price, shipping $x for upto $100 and free above that" on the theory that the profit margin is high enough on high-value orders ... and the Big, Heavy items have specified Freight charges in catalog. But if you're trying to give users the REAL best price and the REAL best shipping fee because they're actively price comparing with shop.yahoo.com, hey, you've got do something else. Good Luck, Bill _______________________________________________ Boston-pm mailing list [EMAIL PROTECTED] http://mail.pm.org/mailman/listinfo/boston-pm
