动态规划之最优配对问题

2024-04-20 12:08

本文主要是介绍动态规划之最优配对问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

ps

昨晚看了紫书上的最优配对问题,对于上面没有对i判断就直接取异或操作百思不得解,本想今天问学长,百度了下,才知道那里是作者写错了,唉,有点唏嘘,学的越多,对待权威越不敢坚信自己了。。。

题意

空间里有n个点P0,P1,…,Pn-1,你的任务是把它们配成n/2对(n是偶数),使得每个点恰好在一个点对中。所有点对中两点的距离之和应尽量小。

思路

因为是对集合进行配对,自然需要记录当前集合的状态,老方法,二进制。
dp(s) = min(dist(i, j) + dp(s-i-j))
i是s集合中最小的元素的下标(最小最大都可以,只是作为检索起点),j是s集合中其他元素的下标
s从1到1左移n再-1进行迭代,因为s-i-j必然小于s,所以直接迭代就可以,连递归都省去了。

因为没有在oj上找到类似的题目,就百度上找到别人做的一组数据,直接copy了,答案无误,正确性暂时未知,如有道友发现问题,还请不吝告之。

测试数据:Input: 
20 
1 2 3 
1 1 1 
5 6 2 
4 7 8 
2 3 1 
1 4 7 
2 5 8 
3 6 9 
1 2 5 
2 3 6 
4 5 2 
7 8 5 
4 5 1 
-1 2 3 
-1 -9 -7 
0 0 0 
100 0 0 
9 5 1 
7 5 3 
5 5 5 Output: 
119.076 

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cmath>
#include <map>using namespace std;#define LL long longconst int N = 29;int x[N], y[N], z[N];
double dist[N][N];
double dp[(1<<N)];void init_dist(int n)
{for(int i=0; i<n; i++)for(int j=i+1; j<n; j++)dist[i][j] = sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])+(z[i]-z[j])*(z[i]-z[j]));
}double solve(int n)
{for(int s=1; s<(1<<n); s++){dp[s] = 1E9;int pos = 0;while(pos<n && !(s&(1<<pos))) ++pos;for(int i=pos+1; i<n; i++)if(s&(1<<i))dp[s] = min(dp[s], dist[pos][i]+dp[s^(1<<pos)^(1<<i)]);}return dp[(1<<n)-1];
}int main()
{int n;cin>>n;for(int i=0; i<n; i++)cin>>x[i]>>y[i]>>z[i];init_dist(n);dp[0] = 0;cout<<solve(n)<<endl;return 0;
}

这篇关于动态规划之最优配对问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/920225

相关文章

好题——hdu2522(小数问题:求1/n的第一个循环节)

好喜欢这题,第一次做小数问题,一开始真心没思路,然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数,不能写作两整数之比*****************************(一开始没想到,小学没学好) 此题1/n肯定是一个有限循环小数,了解这些后就能做此题了。 按照除法的机制,用一个函数表示出来就可以了,代码如下

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始,按照书籍的划分,第10章开始就进入保护模式(Protected Mode)部分了,感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断(Interrupt)的设计,中断的几种方式:外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用: 为了更好的利用处理器的性能。协同快速和慢速设备一起工作

动态规划---打家劫舍

题目: 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。 思路: 动态规划五部曲: 1.确定dp数组及含义 dp数组是一维数组,dp[i]代表

购买磨轮平衡机时应该注意什么问题和技巧

在购买磨轮平衡机时,您应该注意以下几个关键点: 平衡精度 平衡精度是衡量平衡机性能的核心指标,直接影响到不平衡量的检测与校准的准确性,从而决定磨轮的振动和噪声水平。高精度的平衡机能显著减少振动和噪声,提高磨削加工的精度。 转速范围 宽广的转速范围意味着平衡机能够处理更多种类的磨轮,适应不同的工作条件和规格要求。 振动监测能力 振动监测能力是评估平衡机性能的重要因素。通过传感器实时监

缓存雪崩问题

缓存雪崩是缓存中大量key失效后当高并发到来时导致大量请求到数据库,瞬间耗尽数据库资源,导致数据库无法使用。 解决方案: 1、使用锁进行控制 2、对同一类型信息的key设置不同的过期时间 3、缓存预热 1. 什么是缓存雪崩 缓存雪崩是指在短时间内,大量缓存数据同时失效,导致所有请求直接涌向数据库,瞬间增加数据库的负载压力,可能导致数据库性能下降甚至崩溃。这种情况往往发生在缓存中大量 k

软考系统规划与管理师考试证书含金量高吗?

2024年软考系统规划与管理师考试报名时间节点: 报名时间:2024年上半年软考将于3月中旬陆续开始报名 考试时间:上半年5月25日到28日,下半年11月9日到12日 分数线:所有科目成绩均须达到45分以上(包括45分)方可通过考试 成绩查询:可在“中国计算机技术职业资格网”上查询软考成绩 出成绩时间:预计在11月左右 证书领取时间:一般在考试成绩公布后3~4个月,各地领取时间有所不同

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

poj 2976 分数规划二分贪心(部分对总体的贡献度) poj 3111

poj 2976: 题意: 在n场考试中,每场考试共有b题,答对的题目有a题。 允许去掉k场考试,求能达到的最高正确率是多少。 解析: 假设已知准确率为x,则每场考试对于准确率的贡献值为: a - b * x,将贡献值大的排序排在前面舍弃掉后k个。 然后二分x就行了。 代码: #include <iostream>#include <cstdio>#incl

代码随想录冲冲冲 Day39 动态规划Part7

198. 打家劫舍 dp数组的意义是在第i位的时候偷的最大钱数是多少 如果nums的size为0 总价值当然就是0 如果nums的size为1 总价值是nums[0] 遍历顺序就是从小到大遍历 之后是递推公式 对于dp[i]的最大价值来说有两种可能 1.偷第i个 那么最大价值就是dp[i-2]+nums[i] 2.不偷第i个 那么价值就是dp[i-1] 之后取这两个的最大值就是d