位屏蔽动态编程

2024-10-04 07:31:33 发布

您现在位置：Python中文网/ 问答频道 /正文
9113 3

有N个男人和N个女人，都编号为1,2，…，N

对于每个i，j (1≤i、 j≤N） 男人i和女人j的相容性表示为整数ai，j。如果ai，j=1，男人i和女人j是相容的；如果ai，j=0

事实并非如此

芋头正试图使N 成对的，每对由一男一女组成，他们是相容的。在这里，每个男人和每个女人都必须属于一对

如何表示dp的状态


Tags： 状态整数ai编号事实dp正试图男人
1条回答
网友
1楼 · 发布于 2024-10-04 07:31:33

所以你有无向二部图，想要得到完全（完美）匹配

可以使用Ford–Fulkerson algorithm找到它（注意-它不是DP）

DP在完美匹配问题中的应用示例-Hopcroft-Karp algorithm

相关问题 更多 >

    编程相关推荐