带权邮局位置问题: 已知n个点p1,p2,...,pn及与它们相联系的权重w1,w2,...,wn。我们希望能找到一点p(不一定是输入点中的一个),使和式
最小,此处d(a,b)表示点a和点b之间的距离。
对于一维带权邮局位置问题即找带权中位数。如下
// 一维邮局选址问题.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include<iostream>
#include<ctime>
#include<cmath>
#define N 100
using namespace std;
struct Node
{
double value;
double weight;
};
Node nodes[N];
//产生一个随即下标,用其对应的数组元素作为比较标准(即一趟快速的主元)
int random(int m,int n)
{
srand((unsigned)time(NULL));
return m + (rand()%(n-m+1));
}
//一趟快速排序
int qartition(Node *nodes,int begin,int end)
{
int i = begin-1,j=begin;
double x = nodes[end].value;
while(j<end)
{
if(nodes[j].value<=x)
{
i++;
Node temp = nodes[i];
nodes[i]=nodes[j];
nodes[j]=temp;
}
j++;
}
Node temp = nodes[end];
nodes[end]=nodes[i+1];
nodes[i+1]=temp;
return i+1;
}
//一趟随机化快速排序
int random_qartition(Node *nodes,int begin,int end)
{
int q = random(begin,end);
Node temp = nodes[end];
nodes[end]=nodes[q];
nodes[q]=temp;
return qartition(nodes,begin,end);
}
//随机化快速排序
void random_fast_sort(Node *nodes,int begin,int end)
{
if(begin<end)
{
int p = random_qartition(nodes,begin,end);
random_fast_sort(nodes,begin,p-1);
random_fast_sort(nodes,p+1,end);
}
}
//得到带权的中位数
Node GetMidWeight(Node *nodes,int begin,int end,double SumWeight)
{
double midSum = 0.0;
int i;
for(i=begin;i<=end;i++)
{
midSum+=nodes[i].weight;
if(midSum>=SumWeight/2)
break;
}
return nodes[i];
}
int _tmain(int argc, _TCHAR* argv[])
{
int cases;
cout<<"请输入案例个数:"<<endl;
cin>>cases;
while(cases--)
{
cout<<"请输入数据个数:"<<endl;
int n;
cin>>n;
int i;
double sum = 0.0;
cout<<"请输入每一点值和其权值"<<endl;
for(i=0;i<n;i++)
{
cin>>nodes[i].value>>nodes[i].weight;
sum+=nodes[i].weight;
}
random_fast_sort(nodes,0,n-1);
cout<<"邮局位置为:"<<endl;
Node node = GetMidWeight(nodes,0,n-1,sum);
cout<<node.value<<endl;
cout<<"总代价为:"<<endl;
double sumValue = 0.0;
for(i=0;i<n;i++)
{
sumValue+=abs(nodes[i].value-node.value);
}
cout<<sumValue<<endl;
}
system("pause");
return 0;
}
<wbr><wbr><wbr>找出二维带权邮局位置问题的最佳解答,其中所有的点都是(x,y)坐标对,并且点a(x1,y1)与点b(x2,y2)之间的距离是Manhattan距离:d(a,b)=|x1-x2|+|y1-y2|。</wbr></wbr></wbr>
对于二维带权邮局位置问题可以转化为一维邮局位置问题,分别求x、y的带权中位数。见下篇《二维带权邮局位置问题》
分享到:
相关推荐
一维快速傅里叶变换FFT的C++实现,里面是FFT1.cpp函数,用于进行一维数组的FFT。有详细的注释和说明。
用C++语音实现一维数组二维数组写入txt,从txt中读取数据存到一维数组、二维数组,数组用指针表示
可生成 CODE39,CODE93,CODE128A,CODE128B,CODE128C,CODE2of5,CODEEAN13编码格式的一维码
C++实现的二维矩阵卷积运算 主要是一个卷积的算法,矩阵保存在一个二维矩阵中。接口可以根据需要自行修改。提供了2种卷积的算法,被注释掉的那部分执行效率比较低下,对于大矩阵容易造成程序死掉的情况。所以进行了...
例5.3 一维数组输入n个数,计算所有元素的和,求出最大的元素和最小的元素 1 利用for循环,计算输出1+2+…+100的和 2 输出1—100之间所有偶数。 3 输出1—100之间所有奇数。 4 分别计算1--100之间所有的偶数和、...
C++利用OpenGL实现三维绘图,包括详细的代码注释
二维小波变换源代码(C++实现),对学习图像处理非常有用
MFC实现的图形在三维坐标下,进行坐标平移、投影、对称等变换。
一维条形码生成并且保存成bmp图片,以方便打印C++MFC源码.输入数字即可转化成bmp一维码图像,且可在图像上打字.方便做出入库系统用
运用蒙特卡洛的思想来实现一维积分,本文运用C++进行实现算法
1、本文详细描述了C++语言两个一维数组相加求和的方法。 2、通过详细示例,让读者更直观地阅读,更清晰的理解。 3、示例代码可直接复制,编译后可直接运行。 4、根据示例以及运行结果,让读者加强记忆及理解。
主要采用fortran编译了一维黎曼问题的精确解,可用于计算空气动力学计算
资源为二维傅里叶变换的C++实现,内含多个示例,比较详细。
C++实现一维向量旋转算法,主要讲述C++编写的一些向量处理算法
用二维数组实现二维矩阵的加法和乘法 #include #define SIZE 4 void addMatrix(int [ ][SIZE], int [ ][SIZE], int [ ][SIZE]); void mulMatrix(int [ ][SIZE], int [ ][SIZE], int [ ][SIZE]); void ...
用c++实现任意维数的向量的各种操作!对c++初学者来说是一个很好的代码!
计算流体力学经典问题,一维黎曼问题,文档包含代码。
C++实现三维动态数组,赋值,加减乘算法,适用于三维空间对象之间的运算实现。
设有n个人围坐一圈并由1到n编号,从某个人开始报数,数到m的人出列,接着从出列的下一个人开始重新1到n报数,数到m的人又出列,如此反复地报数和出列,直到最后一个人出列为止,设计确定这n个人出列序列的程序
本篇文章是对使用C++实现DBSCAN聚类算法的方法进行了详细的分析介绍,需要的朋友参考下