[底部更新（包括解决方案源代码）]
我有一个计算机可以帮助解决的具有挑战性的业务问题。
沿着山区流淌着一条蜿蜒曲折的长河，水流强劲。沿着河流的某些部分，有一片对环境敏感的土地，适合种植一种特殊类型的稀有水果，这种水果的需求量非常大。一旦田间劳动者收获水果，时钟就开始滴答作响，将水果送到加工厂。尝试将水果运送到上游或陆上或空中是非常昂贵的。到目前为止，将它们运送到工厂的最具成本效益的机制是在下游的容器中，该容器仅由河流的恒流供电。我们有能力建造 10 个加工厂，需要将这些加工厂设在河边，以尽量减少水果在运输过程中的总时间。然而，这些水果可能需要很长时间才能到达最近的下游工厂，但那段时间直接损害了它们的销售价格。实际上，我们希望最小化到最近的相应下游工厂的距离总和。植物可以位于水果接入点下游低至 0 米处。
问题是：为了利润最大化，如果我们找到了 32 个水果种植区，那么 10 个加工厂应该在河流上游多远，这些区域到河底上游的距离（米）：10 , 40, 90, 160, 250, 360, 490, ... (n^2)*10 ... 9000, 9610, 10320？
[希望所有致力于解决这个问题以及创建类似问题和使用场景的工作都可以帮助提高人们对软件/商业方法专利的破坏性和扼杀性质的认识并产生普遍的抵制（无论这些专利在多大程度上被相信在当地是合法的）。]
更新
更新2：我写的一个算法在几分之一秒内给出了答案，我相信它相当好（但它在样本值上还不稳定）。稍后我会提供更多细节，但简短如下。将植物以相等的间距放置。循环遍历所有内部植物，在每个植物上，您通过测试其两个邻居之间的每个位置来重新计算其位置，直到在该空间内解决问题（贪心算法）。因此，您优化工厂 2，保持 1 和 3 固定。然后工厂 3 保持 2 和 4 固定......当你到达终点时，你循环回来并重复，直到你进入一个完整的循环，每个加工厂的重新计算位置停止变化。同样在每个循环结束时，你尝试移动紧挨着拥挤的加工厂，而且都在彼此附近 水果堆到远处有水果堆的地区。有很多方法可以改变细节，从而产生准确的答案。我有其他候选算法，但都有故障。[我稍后会发布代码。] 就像下面提到的 Mike Dunlavey 一样，我们可能只想要“足够好”。
给出一个可能是“足够好”的结果的想法：
10010 total length of travel from 32 locations to plants at
{10,490,1210,1960,2890,4000,5290,6760,8410,9610}
更新 3：mhum 首先给出了正确的精确解，但（还）没有发布程序或算法，所以我写了一个产生相同值的程序或算法。
/************************************************************
This program can be compiled and run (eg, on Linux):
$ gcc -std=c99 processing-plants.c -o processing-plants
$ ./processing-plants
************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//a: Data set of values. Add extra large number at the end
int a[]={
10,40,90,160,250,360,490,640,810,1000,1210,1440,1690,1960,2250,2560,2890,3240,3610,4000,4410,4840,5290,5760,6250,6760,7290,7840,8410,9000,9610,10240,99999
};
//numofa: size of data set
int numofa=sizeof(a)/sizeof(int);
//a2: will hold (pt to) unique data from a and in sorted order.
int *a2;
//max: size of a2
int max;
//num_fixed_loc: at 10 gives the solution for 10 plants
int num_fixed_loc;
//xx: holds index values of a2 from the lowest error winner of each cycle memoized. accessed via memoized offset value. Winner is based off lowest error sum from left boundary upto right ending boundary.
//FIX: to be dynamically sized.
int xx[1000000];
//xx_last: how much of xx has been used up
int xx_last=0;
//SavedBundle: data type to "hold" memoized values needed (total traval distance and plant locations)
typedef struct _SavedBundle {
long e;
int xx_offset;
} SavedBundle;
//sb: (pts to) lookup table of all calculated values memoized
SavedBundle *sb; //holds winning values being memoized
//Sort in increasing order.
int sortfunc (const void *a, const void *b) {
return (*(int *)a - *(int *)b);
}
/****************************
Most interesting code in here
****************************/
long full_memh(int l, int n) {
long e;
long e_min=-1;
int ti;
if (sb[l*max+n].e) {
return sb[l*max+n].e; //convenience passing
}
for (int i=l+1; i<max-1; i++) {
e=0;
//sum first part
for (int j=l+1; j<i; j++) {
e+=a2[j]-a2[l];
}
//sum second part
if (n!=1) //general case, recursively
e+=full_memh(i, n-1);
else //base case, iteratively
for (int j=i+1; j<max-1; j++) {
e+=a2[j]-a2[i];
}
if (e_min==-1) {
e_min=e;
ti=i;
}
if (e<e_min) {
e_min=e;
ti=i;
}
}
sb[l*max+n].e=e_min;
sb[l*max+n].xx_offset=xx_last;
xx[xx_last]=ti; //later add a test or a realloc, etc, if approp
for (int i=0; i<n-1; i++) {
xx[xx_last+(i+1)]=xx[sb[ti*max+(n-1)].xx_offset+i];
}
xx_last+=n;
return e_min;
}
/*************************************************************
Call to calculate and print results for given number of plants
*************************************************************/
int full_memoization(int num_fixed_loc) {
char *str;
long errorsum; //for convenience
//Call recursive workhorse
errorsum=full_memh(0, num_fixed_loc-2);
//Now print
str=(char *) malloc(num_fixed_loc*20+100);
sprintf (str,"\n%4d %6d {%d,",num_fixed_loc-1,errorsum,a2[0]);
for (int i=0; i<num_fixed_loc-2; i++)
sprintf (str+strlen(str),"%d%c",a2[ xx[ sb[0*max+(num_fixed_loc-2)].xx_offset+i ] ], (i<num_fixed_loc-3)?',':'}');
printf ("%s",str);
return 0;
}
/**************************************************
Initialize and call for plant numbers of many sizes
**************************************************/
int main (int x, char **y) {
int t;
int i2;
qsort(a,numofa,sizeof(int),sortfunc);
t=1;
for (int i=1; i<numofa; i++)
if (a[i]!=a[i-1])
t++;
max=t;
i2=1;
a2=(int *)malloc(sizeof(int)*t);
a2[0]=a[0];
for (int i=1; i<numofa; i++)
if (a[i]!=a[i-1]) {
a2[i2++]=a[i];
}
sb = (SavedBundle *)calloc(sizeof(SavedBundle),max*max);
for (int i=3; i<=max; i++) {
full_memoization(i);
}
free(sb);
return 0;
}