题目大意:
一场比赛中,将所有参赛选手进行分组,两个人一组,每个选手都有自己的一个坐标,要求每组中两个人之间的距离尽量接近,并且将所有小组的距离相加,使得总的的距离和最小。
解题思路:
集合上的动态规划问题,需要对集合进行子集遍历。设d[S]代表集合S中的元素进行两两配对的最小距离和,则状态转移方程为:
d(S) = min{ | PiPj | + d( S - {i} - {j} ) | j in S, i = max{S} or i = min{S} }
其中,PiPj表示选手 i 和选手 j 之间的距离,i 的取值为S中的最大元素或者最小元素,若 i 为最小元素,则 j 从 i+1开始遍历,因为 i 为最小,那么 i+1 开始,以后的元素均比 i 大,若 i 为最大元素,则 j 从 i-1开始,同理。
代码:
#include <iostream> #include <algorithm> #include <vector> #include <string> #include <cmath> #include <fstream> #include <sstream> #include <map> #include <set> #include <iomanip> using namespace std; #define LOOP(X,Y) for( int X = 0; X < Y; X++ ) #define LOOPP(X, Y, Z) for( int X = Y; X < Z; X++ ) #define OPENFILE(PATH) ifstream fin; fin.open(PATH) #define PB push_back #define ULL unsigned long long #define LL long long double p[21][2]; double d[99999]; double Distance[21][21]; double dist( int i, int j ) { return ( hypot(p[i][0] - p[j][0], p[i][1] - p[j][1]) ); } int main() { OPENFILE( "test.txt" ); if( !fin.is_open() ) return 0; string line; string name; double X, Y; int T; istringstream is; while( 1 ) { is.clear(); memset( p, 0.0, sizeof( p ) ); memset( d, 0.0, sizeof( d ) ); getline( fin, line ); is.str( line ); is>>T; if( !T ) break; T *= 2; LOOP( i, T ) { is.clear(); getline( fin, line ); is.str( line ); is>>name>>X>>Y; p[i][0] = X; p[i][1] = Y; } for( int i = 0; i < T; i++ ) { for( int j = 0; j < T; j++ ) Distance[i][j] = dist( i, j ); //实现计算出两两之间的距离 } d[0] = 0; //用二进制进行“子集枚举” for( int S = 1; S < (1<<T); S++ ) { int i, j; d[S] = 99999; for( i = 0; i < T; i++ ) { if( S & (1<<i) ) //找出S中最小的 i break; } for( j = i+1; j < T; j++ ) { if( S & (1<<j) ) //若 j 在 S 中 d[S] = min( d[S], Distance[i][j] + d[S ^ (1<<i) ^ (1<<j)] ); } } cout<<setiosflags(ios::fixed)<<setprecision(2)<<d[(1<<T)-1]<<endl; } return 0; }
相关推荐
The book provides a thorough coverage of the subject including major sub-areas such as sub-band adaptive beamforming, frequency invariant beamforming, blind wideband beamforming, beamforming without ...
这是一个有关qpsk的beamforming的代码程序,可以通过它得到波束成形和不波束成形的对比图,有利于学习beamforming
Forming Analysis Wizard For CHS
beamforming.rar
Beamforming for the sound localization
宽带波束形成的经典书籍,文章深入浅出的讲解 Adaptive Wideband Beamforming ;Subband Adaptive Beamforming ;Design of Fixed Wideband Beamformers ;Frequency Invariant Beamforming ; Blind Wideband Beam...
Robust Adaptive Beamforming: Jian Li, Petre Stoica Wiley-Interscience
Wideband Beamforming
A Primer on Digital Beamforming.PDF
基于GSC的波束形成算法 有旁瓣抑制的效果
Beamforming Forming源码.zip
无线通信中的beamforming,很不错的一片论文
Abstract—A random beamforming (RBF) technique is proposed to achieve omnidirectional coverage for broadcast channels in multipleantenna systems. In the proposed scheme, the time and frequency ...
Digital Beamforming in wireless communication(第三部分)
matlab robust adaptive beamforming and multiuser detection
用python编写了两维阵列的波束赋形图,其中假设单阵子为理想阵子,天线间距为1/2 lamda,当然你们都可以修改,
matlab 代码 beamforming 波束赋形 多种波束成形算法比较 以及多种天线数量比较 均匀线阵方向图 %8阵元均匀线阵方向图,来波方向为0度 clc; clear all; close all; imag=sqrt(-1); element_num=8;%阵元数为8 d_lamda...
Optimal Beamforming in MIMO
matlab 代码 beamforming 波束赋形 多种波束成形算法比较 以及多种天线数量比较
GSC based beamforming