最優(yōu)倉(cāng)庫(kù)布局方案實(shí)驗(yàn) 動(dòng)態(tài)規(guī)劃 算法設(shè)計(jì)

1、描述  A公司沿著高速公路開設(shè)了n 個(gè)連鎖超市1,2,n.這n 個(gè)超市距公司總部的距離分別為d1 < d2 << dn.公司總部決定近期在這n 個(gè)超市中選擇m 個(gè)超市來(lái)增設(shè)貨品倉(cāng)庫(kù).每個(gè)倉(cāng)庫(kù)可以為若干個(gè)超市提供貨物,且每個(gè)超市恰有1 個(gè)倉(cāng)庫(kù)為其供貨. 設(shè)為第k個(gè)超市供貨的倉(cāng)庫(kù)位于超市f (k),其送貨距離g(k)=|d(k)- d f (k ) |,公司總部認(rèn)為最優(yōu)的倉(cāng)庫(kù)布局方案應(yīng)使總送貨距離g(k)(1<=k<=n)達(dá)到最小的最優(yōu)倉(cāng)庫(kù)布局方案。      對(duì)于給定的n 個(gè)超市距公司總部的距離d1 < d2

2、<< dn 和欲設(shè)置的倉(cāng)庫(kù)數(shù)m <=n ，計(jì)算出使總送貨距離g(k)(1<=k<=n)達(dá)到最小的最優(yōu)倉(cāng)庫(kù)布局方案。 輸入第1 行中的2 個(gè)整數(shù)為n和m，且滿足1 <= n <= 200,1<= m<= 130,m<= n。接下來(lái)的n行中每行一個(gè)整數(shù)，依次為d1, d2, , dn 。輸出將計(jì)算出的最小總送貨距離輸出樣例輸入6 35612192027樣例輸出8代碼：#include "stdafx.h"#include "stdio.h"#include&l

3、t;string.h>#include<algorithm>using namespace std; int a105,minvalue; int dp105105;int Min(int b,int n,int m) int min=bn-1,j;for(j=n-1;j>=m-1;j-) if(bj<min) min=bj;return min; ;int f(int n,int m) if(dpnm!=-1) return dpnm; int b105,j,p;if(m=1) p=an-a1; dpnm=p; return p; if(m=n) dpnm=0;

4、 return 0; else for(j=n-1;j>=m-1;j-)p=an-aj+1; bj=f(j,m-1)+p; dpnm=Min(b,n,m);return dpnm;int main() int i,n,m; scanf("%d",&n); scanf("%d",&m);a0=0; for(i=1;i<=n;i+) scanf("%d",&ai);/* j=i; while(aj<aj-1) tap=aj; aj=aj-1; aj-1=tap; j-; */ / QuickSort(a,1,n); / MergeSort(a,n+1); sort(a+1,a+n+1); memset(dp,-1,sizeof(dp); / for(i=1;i<=n;i+) / printf("%d"