带权邮局位置问题: 已知n个点p1,p2,...,pn及与它们相联系的权重w1,w2,...,wn。我们希望能找到一点p(不一定是输入点中的一个),使和式
最小,此处d(a,b)表示点a和点b之间的距离。
找出二维带权邮局位置问题的最佳解答,其中所有的点都是(x,y)坐标对,并且点a(x1,y1)与点b(x2,y2)之间的距离是Manhattan距离:d(a,b)=|x1-x2|+|y1-y2|。
对于二维带权邮局位置问题可以转化为一维邮局位置问题,分别求x、y的带权中位数。
// 二维带权邮局位置(选址)问题.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 XValue;
double YValue;
double weight;
};
Node nodes[N];
//产生一个随即下标,用其对应的数组元素作为比较标准(即一趟快速的主元)
int random(int m,int n)
{
srand((unsigned)time(NULL));
return m + (rand()%(n-m+1));
}
//一趟快速排序
//flag为0表示求横坐标的排序,为1表示纵坐标的排序
int qartition(Node *nodes,int begin,int end,bool flag)
{
if(!flag)
{
int i = begin-1,j=begin;
double x = nodes[end].XValue;
while(j<end)
{
if(nodes[j].XValue<=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;
}
else
{
int i = begin-1,j=begin;
double y = nodes[end].YValue;
while(j<end)
{
if(nodes[j].YValue<=y)
{
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,bool flag)
{
int q = random(begin,end);
Node temp = nodes[end];
nodes[end]=nodes[q];
nodes[q]=temp;
return qartition(nodes,begin,end,flag);
}
//随机化快速排序
void random_fast_sort(Node *nodes,int begin,int end,bool flag)
{
if(begin<end)
{
int p = random_qartition(nodes,begin,end,flag);
random_fast_sort(nodes,begin,p-1,flag);
random_fast_sort(nodes,p+1,end,flag);
}
}
//得到带权的中位数
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<<"请输入每一点位置(x,y)和其权值"<<endl;
for(i=0;i<n;i++)
{
cin>>nodes[i].XValue>>nodes[i].YValue>>nodes[i].weight;
sum+=nodes[i].weight;
}
random_fast_sort(nodes,0,n-1,0);
Node node = GetMidWeight(nodes,0,n-1,sum);
double xValue = node.XValue;
random_fast_sort(nodes,0,n-1,1);
node = GetMidWeight(nodes,0,n-1,sum);
double yValue = node.YValue;
cout<<"邮局位置为:"<<endl;
cout<<"( "<<xValue<<","<<yValue<<" )"<<endl;
cout<<"总代价为:"<<endl;
double sumValue = 0.0;
for(i=0;i<n;i++)
{
sumValue+=abs(nodes[i].XValue-xValue)+abs(nodes[i].YValue-yValue);
}
cout<<sumValue<<endl;
}
system("pause");
return 0;
}
分享到:
相关推荐
MFC实现的图形在三维坐标下,进行坐标平移、投影、对称等变换。
二维小波变换源代码(C++实现),对学习图像处理非常有用
各种三维变换算法,包括:几何变换:平移、旋转、变比、对称、错切。投影变换:平行投影(三视图、正轴测图、斜轴测图)、透视图。
C++实现的二维矩阵卷积运算 主要是一个卷积的算法,矩阵保存在一个二维矩阵中。接口可以根据需要自行修改。提供了2种卷积的算法,被注释掉的那部分执行效率比较低下,对于大矩阵容易造成程序死掉的情况。所以进行了...
二维离散高斯卷积的一个实现
主要包括一个初始化种子函数 void InitSeed(); 和两个二维随机点生成函数 PointStruct GetUniformPoint2( ); PointStruct GetNormalPoint2( ) ...实现了生成服从二维均匀分布和二维标准正态分布随机点的功能。
邮局选址c++设给定的n个居民点的位置坐标为:(x0,y0),(x1,y1),...,(xn-1,yn-1)。用x 坐标表示东西向,用y坐标表示南北向。各居民点的位置可以由坐标(x,y)表示。...邮局选址问题实际上是求中位数的问题。
资源为二维傅里叶变换的C++实现,内含多个示例,比较详细。
C++二维数组实现杨辉三角的前10行输出
本程序用VC++实现,可以实现平移旋转和比例变换
用C++语音实现一维数组二维数组写入txt,从txt中读取数据存到一维数组、二维数组,数组用指针表示
c#调用c++DLL,DLL里是二维数组 ,c#里如何调用二维数组
二维灰度图像的小波变换和逆变换的C++实现,包括源码和编译后程序,可直接运行
图形学 二维图形的几何变换 对称平移缩放旋转 矩阵实现 C++
如果有疏忽或错误的地方...这里一共设计了两个类:Location,Point,分别代表二维和三维坐标(向量)类。 对类的+ - * / >> 都进行了重载。 大部分函数使用及功能都有详细说明,注释内容说明的均是上个函数和语句的功能
在c++中,经常调用函数,而子函数经常要返回的值是数组,无论一维数组还是二维数组都需要运用到指针的知识。一维数组不再过多叙述,给了一个实例如何返回二维数组,希望对大家有帮助(主要用到指针的知识,看不懂的...
实现2-10标准二维表问题.cpp
.DOC 二维平面图形设计 c++课程设计
实现二维三维图形的变换。共计有7到8个代码。可以先看下运行好的exe
二维坐标转换