[底部更新（包括解决方案源代码)]
我有一个具有挑战性的业务问题，计算机可以帮助解决。
沿着山区，有一条蜿蜒曲折的长河，水流湍急。沿着河流的某些部分有一些环境敏感的土地，适合种植需求量很大的特定类型的稀有水果。一旦田间劳动者收获了水果，就开始将水果运送到加工厂。尝试将水果向上游或通过陆地或空中运送的成本非常高。到目前为止，将它们运送到工厂的最具成本效益的机制是使用仅由河流恒流驱动的下游集装箱。我们有能力建造 10 个加工厂，需要将这些加工厂建在河边，以尽量减少水果在运输途中的总时间。水果可能需要很长时间才能到达最近的下游工厂，但这段时间会直接影响它们的销售价格。实际上，我们希望最小化到最近的各个下游工厂的距离总和。工厂可以位于距离水果接入点下游 0 米处。
问题是：如果找到了32个水果种植区，那么为了利润最大化，这10个加工厂应该建在河上游多远的地方，这些水果种植区到河床上游的距离是（米）：
10, 40, 90, 160, 250, 360, 490, ... (n^2)*10 ... 9000, 9610, 10320？
[希望所有致力于解决这一问题以及创造类似问题和使用场景的工作都能够帮助提高人们对软件/商业方法专利的破坏性和窒息性的认识并产生普遍的抵制（无论这些专利在何种程度上可能被相信）在当地是合法的）。]
UPDATES
Update1：忘记补充：我相信这个问题是一个特例this one https://stackoverflow.com/questions/5167774/minimize-the-sum-of-errors-of-representative-integers/5958885#5958885.
更新2：我编写的一个算法在不到一秒的时间内给出了答案，我相信它相当好（但它在样本值上还不稳定）。我稍后会提供更多详细信息，但简短如下。将植物以相等的间距放置。循环遍历所有内部植物，在每个植物上，您通过测试其两个邻居之间的每个位置来重新计算其位置，直到问题在该空间内得到解决（贪婪算法）。因此，您可以在固定 1 和 3 的情况下优化工厂 2。然后工厂 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}
Update3：嗯，首先给出了正确的精确解决方案，但（尚未）发布程序或算法，所以我写了一个产生相同值的程序或算法。
/************************************************************
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;
}
