最小化运输时间

10010 total length of travel from 32 locations to plants at 
{10,490,1210,1960,2890,4000,5290,6760,8410,9610}

/************************************************************
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;
}