kub*_*tto 3 algorithm matrix dynamic-programming
我有一个动态编程(可能是贪婪的)问题.
设A是mxn矩阵.令k为整数,使得k≤min{m,n}.
找到A的k个元素,使得这些k个元素中的每一个都在它们唯一的列和行中; 并且这些k元素的总和被最小化.
换句话说,我想从A中选择k个元素,使得它们的总和最小; 但如果我选择A 2,3那么我就不能选择A 2,6或A 4,3.
贪婪的方法似乎是选择A中的最小元素,删除其行和列,并重复直到A'耗尽'.但是,在这种情况下,我无法证明贪婪的选择属性,或者它是否具有贪婪的选择属性.
我也无法弄清楚如何为DP解决方案构建表.
如果此问题已经提出并且有特定名称,请您分享一下吗？
贪婪不会削减它.你需要匈牙利算法机器.人们可以考虑创建n-k个新行和m-k个新列,使得新行 - 新列条目非常不具吸引力,而其他新条目非常有吸引力.然后找到一个最低成本的解决方案,该解决方案将列与列一对一地匹配,并丢弃包含新行或列的对.
在实际操作中,会有更好的实施,但描述它需要我回顾一下HA的细节.