关键词：
有一个送外卖的，他手上有n份订单，他要把n份东西，分别送达n个不同的客户的手上。n个不同的客户分别在1~n个编号的城市中。送外卖的从0号城市出发，然后n个城市都要走一次（一个城市可以走多次），最后还要回到0点（他的单位），请问最短时间是多少。现在已知任意两个城市的直接通路的时间。
第一行一个正整数n （1<=n<=15）
接下来是一个（n+1）*(n+1)的矩阵，矩阵中的数均为不超过10000的正整数。矩阵的i行j列表示第i-1号城市和j-1号城市之间直接通路的时间。当然城市a到城市b的直接通路时间和城市b到城市a的直接通路时间不一定相同，也就是说道路都是单向的。
一个正整数表示最少花费的时间
3 0 1 10 10 1 0 1 2 10 1 0 10 10 2 10 0
8
1<=n<=15
分类标签 Tags 点此展开
思路：
首先题目给出了邻接矩阵，而且还说每个点可以访问多次，那么我们考虑两点间的距离便只考虑最短距离，不考虑怎么到的方式和路径 选择Floyd 算法求出两点间的最短距离
题目数据量较小 先考虑搜索 那么解答树将会是n个节点的全排列 数量达到 n！而且不好剪枝 而且这样想还有一定的问题 题目上说一个点可以经历很多次以达到最短路 那么解答树将不是排列 而是集合的形式 那么搜索就很难解决这道题 并且很明显感到有重叠子问题 那么开始考虑动归
如果用dp的话 要考虑状态数量和状态的划分和表示 那么由搜索的猜想可以感觉到需要集合 状态可能就要表示为当前集合S中的元素已经全部经历过的最短路径 并且应该记下来集合S中最后一个访问的元素是什么 因为这样的话可以方便的递推出下一个状态最终解决问题 并且题目给出两点最短距离 记下了最后一个访问的点 每一个状态就可以由上一个状态得出 那么状态转移方程：
dp [ 集合S(不包含j) ] [ 要访问的点j ] (表示集合S中的点已经访问，且最后访问的是j的最短路长度)= min { dp [ 已经访问过的集合S‘ (S‘中没有点j，也没有点i) ] [ S‘集合中最后一个访问的点是 i ] +dis [ i ] [ j ] }
其中i属于S枚举(ATT!！ i属于S 不属于S‘ 这里要多理解)就好 就可以开始递推了
并且问题的答案 就应该在dp[集合S包括除了0的所有点][最后一个访问的是0号点]
dp的实现：
首先考虑集合如何表示 如果用数组的话 那么数量是惊人的 因为每个点可以重复 并且无法估计需要的大小 集合 集合有一个性质就是无序性 集合中有 只代表有 没有顺序 这也解释了为什么上文说要记下来最后一个访问的点 那么选择用二进制来表示和压缩状态
上代码：
#include<cstdio> #include<cstring> #include<iostream> using namespace std; #define N 1<<16 #define nn 16 int d[nn][nn],f[N][nn]; int main () { //状态压缩 二进制位表示对应状态 编号n对应的二进制位为1<<n 那一位上是1表示遍历过 是0表示还没有遍历 /*f[s][i]表示已经遍历的元素在s（二进制数）中 i为最后遍历的编号 则f[s][i]的值表示s中的元素已经遍历完， 且刚访问完i的最短路长度*/ int n;//节点数量 cin>>n; for (int i=0; i<=n; i++) for (int j=0; j<=n; j++) cin>>d[i][j];//输入已经给出的两个节点的距离 for (int k=0; k<=n; k++) for (int i=0; i<=n; i++) for (int j=0; j<=n; j++) { if (i!=k&&j!=k&&i!=j) { d[i][j]=min(d[i][j],d[i][k]+d[k][j]);//Floyd 求出i到j的最短路长度记在d[i][j]中 } } int maxx=(1<<(n+1))-1; //最大的状态数 即(1<<(n+1))-1 对应的二进制数(n位)上每一位为1 for (int i=0; i<N; i++) for (int j=0; j<nn; j++) f[i][j]=0x6ffffff;//初始化 所有情况的距离初始化为最大值 for (int i=0; i<=n; i++) f[0][i]=d[0][i]; /*初始化 s集合中没有点 只刚遍历完i点的最短路值即为d[0][i](0号点到i的最短路) (这是动归的基础起点与边界) 因为题目要求从0号点出发 也是为什么答案在f[集合s有除了0号点的所有点][0] 代表所有点全部访问完并且最后一个访问的是0号点 符合题目所说从0出发访问再回到0的最短距离*/ for (int s=1; s<=maxx; s++) //枚举所有状态 for (int j=0; j<=n; j++) //访问还不在s中的点j 去更新f if (!((1<<j)&s)) { //如果j在s里 不访问 for (int i=0; i<=n; i++) { //从s中的点（i属于集合s） 出发去更新到j的距离 if (s&(1<<i)) { //i在s中 f[s][j]=min(f[s][j],f[s^(1<<i)][i]+d[i][j]); //异或即可求出补集（或者叫集合的减法）s^(1<<i) 表示把s集合中的i去掉 } } } /// int mmax=0x7fffffff; // for(int i=1; i<=n; i++) // mmax=min(mmax, f[maxx^(1<<i)][i]+d[i][0]); // cout<<mmax<<" "; //如果下面的最终结果不理解 尝试理解下这一种输出 其实两者是一致的一样的 可以帮助你理解下面 cout<<f[maxx^1][0]; //s集合中有除0号点以外的所有元素，最后一个访问的元素为0号 即为所求 return 0; }
/*-------------------------------------------------*/
最小总代价
描述
n个人在做传递物品的游戏,编号为1-n。
游戏规则是这样的：开始时物品可以在任意一人手上，他可把物品传递给其他人中的任意一位；下一个人可以传递给未接过物品的任意一人。
即物品只能经过同一个人一次，而且每次传递过程都有一个代价；不同的人传给不同的人的代价值之间没有联系；
求当物品经过所有n个人后，整个过程的总代价是多少。
格式
输入格式
第一行为n,表示共有n个人（16>=n>=2）；
以下为n*n的矩阵，第i+1行、第j列表示物品从编号为i的人传递到编号为j的人所花费的代价，特别的有第i+1行、第i列为-1（因为物品不能自己传给自己），其他数据均为正整数(<=10000)。
(对于50%的数据，n<=11)。
输出格式
一个数，为最小的代价总和。
样例1
样例输入1
2
-1 9794
2724 –1
样例输出1
2724
限制
所有数据时限为1s
【算法分析】
看到2<=n<=16，应想到此题和状态压缩dp有关。每个人只能够被传递一次，因此使用一个n位二进制数state来表示每个人是否已经被访问过了。但这还不够，因为从这样的状态中，并不能清楚地知道现在物品在谁 的手中，因此，需要在此基础上再增加一个状态now，表示物品在谁的手上。
dp[state][now]表示每个人是否被传递的状态是state，物品在now的手上的时候，最小的总代价。
初始状态为：dp[1<<i][i]=0；表示一开始物品在i手中。
所求状态为：min(dp[(1<<n)-1][j]); 0<=j<n
状态转移方程是：
dp[state][now]=min(dp[pre][t]+dist[now][t])；
pre表示的是能够到达state这个状态的一个状态，t能够传递物品给now且只有二进制下第t位与state不同。
状态的大小是O((2n)*n)，转移复杂度是O(n)。总的时间复杂度是O((2n)*n*n)。
上代码：
#include<cstdio> #include<cstring> #include<iostream> using namespace std; int n,e[20][20]; int f[70010][20];//f[state][now]表示每个人是否被传递的状态是state，物品在now的手上的时候，最小的总代价。 int min(int a,int b) { if(a==-1) return b; if(b==-1) return a; return a>b ? b:a; } int main() { scanf("%d",&n); for(int i=0; i<n; i++) for(int j=0; j<n; j++) scanf("%d",&e[i][j]); memset(f,-1,sizeof(f)); for(int i=0; i<n; i++) //dp[1<<i][i]=0；表示一开始物品在i手中 f[1<<i][i]=0; int ans=-1; for(int i=0; i< 1<<n; i++) //枚举第i个人状态 for(int j=0; j<n; j++) //第j个人接到 if(f[i][j]!=-1) for(int k=0; k<n; k++) //第k个人传过来 if(!(i & (1<<k) )) { f[i | (1<<k)][k] = min(f[i | (1<<k)][k],f[i][j]+e[j][k]); if((i | (1<<k))==(1<<n)-1) ans=min(ans,f[i|(1<<k)][k]); } if(ans!=-1) printf("%d ",ans); else printf("0 "); return 0; }
自己选的路，跪着也要走完！！！
动态规划---状压dp2(代码片段)
今天模拟，状压dp又没写出来。。。还是不会啊，所以今天搞一下这个状压dp。这里有一道状压dp的板子题：CornFields就是一道很简单的状压裸题，但是要每次用一个二进制数表示一行的状态。附加一个关于位运算的总结：上题干... 查看详情
状压dp(代码片段)
这几天都在学习状压DP，总结一下，首先是状压DP的工具。类型符号规则例子按位与&同1为1，其余为09 00001001&5 000001011 &nb 查看详情
foreignnumber[状压dp]
...leInput 123455SampleOutput 24HINT Solution 我们运用状压DP，令f[j][opt]表示当前余数为j，状态为opt的方案。 状态记录的是：各个数字被用了几次。 那么我们就可以状压了。先 查看详情
第一次接触状压dp(代码片段)
状压DP入门及理解*（另类的暴力）* 一般状态数不多的时候就会开数组，但是有的状态并不好表示，于是，状压DP就产生了。 状压DP应该是分两类的，一类是压缩状态，另一类是舍弃状态。 &... 查看详情
算法复习——状压dp
状压dp的核心在于，当我们不能通过表现单一的对象的状态来达到dp的最优子结构和无后效性原则时，我们可能保存多个元素的有关信息··这时候利用2进制的01来表示每个元素相关状态并将其压缩成2进制数就可以达到目的····... 查看详情
fzu2188状压dp
G-SimpleStringProblemTimeLimit:2000MS MemoryLimit:32768KB 64bitIOFormat:%I64d&%I64uSubmitStatusPracticeFZU2218DescriptionRecently,youhavefoundyourinte 查看详情
dp-状压dp(代码片段)
...w.bilibili.com/video/BV1Z4411x7Kw?from=search&seid=13855865082722302053状压介绍：状态表示： 转移方程：i是当前节点，j是下一步要走的节点 子集枚举：核心代码：1。由当前枚举未知首先枚举状态，枚举S中包含的节点：枚... 查看详情
d.romanandnumbers(状压dp)(代码片段)
D.RomanandNumbers(状压dp)把nnn的每一位状压，问题等价于选择一个顺序走完这cntcntcnt个位使得(modm)=0\\pmodm=0(modm)=0答案。令dp[i][j]dp[i][j]dp[i][j]表示状态iii模mmm余jjj的答案。转移时需要注意最高位对应的数不能为000。初始化... 查看详情
poj2411mondriaan'sdream（状压dp）
【POJ2411】Mondriaan‘sDream（状压dp）TimeLimit:3000MS MemoryLimit:65536KTotalSubmissions:14107 Accepted:8152DescriptionSquaresandrectanglesfascinatedthefamousDutchpainterPietMondriaan.Onenight,aft 查看详情
simplestringproblem（状压dp）(代码片段)
SimpleStringProblemRecently,youhavefoundyourinterestinstringtheory.Hereisaninterestingquestionaboutstrings.YouaregivenastringSoflengthnconsistingofthefirstklowercaseletters.Youarerequiredtofindtwonon- 查看详情
状压dp初探·总结
...最优还是最优，无后还是无后，所以它比较好理解。 状压，顾名思义就是要将一些状压想办法压缩起来（可以压，也可以删）。其中这些状态都满足相似性和数量很多。这样才好压而且压得有意义。常见于一般的方格题，网 查看详情
各种dp分类整理
各种dp分类整理数位dp因为比较重要，单独写一篇见这篇状压dp某篇学术垃圾中指出，我们可以说，所有的dp都会有一个“状压”。只不过普通的dp压缩的比较浅显，而使用二进制的状压dp压的比较复杂，才叫它“状压dp”所以这里... 查看详情
b.littleponyandharmonychest(状压dp)(代码片段)
B.LittlePonyandHarmonyChest(状压dp)考虑bi≥59b_i\\ge59bi≥59时，bi=1b_i=1bi=1更优。所以只需考虑bi≤59b_i\\le59bi≤59。又因为bbb数组两两互质。即每个质因子只能被一个数使用。且≤59\\le59≤59的质因子只有161616个。考虑... 查看详情
poj2441状压dp
ArrangetheBullsTimeLimit: 4000MS MemoryLimit: 65536KTotalSubmissions: 5289 Accepted: 2033DescriptionFarmerJohnson‘sBullsloveplayingbasketballverymuch.Butnoneofthemw 查看详情
poj2411状压dp经典
Mondriaan‘sDreamTimeLimit:3000MS MemoryLimit:65536KTotalSubmissions:16771 Accepted:9683DescriptionSquaresandrectanglesfascinatedthefamousDutchpainterPietMondriaan.Onenight,afterproducingthed 查看详情
zoj3471mostpowerful（状压dp）
Recently,researchersonMarshavediscoveredNpowerfulatoms.Allofthemaredifferent.Theseatomshavesomeproperties.Whentwooftheseatomscollide,oneofthemdisappearsandalotofpowerisproduced.Researchersknowthewayev 查看详情
jzoj3747(状压dp)
这题是一道状压DP,暂时还不是很懂.#include<cstdio>#include<cstring>#include<iostream>usingnamespacestd;constintLENM=1010,N=11,M=1e9+7;chars[N];intn,m,u,ind[200],f[LENM][1<<10],g[N],ans[N],gg[N 查看详情
状压dp
poj3254：裸#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>usingnamespacestd;#definerep(i,n)for(inti=1;i<=n;i++)#defineclr(x,c)memset(x,c,sizeof(x))const 查看详情