不回头只选择一个解决方案的算法

Question

例如，有一个 4x4 的整数数组，我需要从每行中选择一个数字，以便每个选定的数字在不同的列中，并且所选数字的总和尽可能低。有问题的网格如下所示：

 1 2 3 1
 2 3 1 3
 2 2 1 2
 3 4 1 9 

我的程序返回以下答案：

1* 2 3 1
2 3* 1 3
2 2 1* 2
3 4 1  9*

但最好的解决方案是：

 1 2 3 1*
 2 3 1* 3
 2* 2 1 2
 3 1* 1 9

我需要在我的功能中更改什么？

 struct r{
    bool moze;
    int quantity;
};
int ff,m1;
bool check(int n,r **tab, int k)
{
    for(int i=0;i<n;i++){
        if(tab[k][i].moze==true || tab[i][ff].moze==true)
            return false;
    }
    return true;
}
bool back(int n, r ** tab, int k){
    for(int i=0;i<n;i++){
        if (check(n,tab,k)){
            tab[k][i].moze=true;
            if (k==n-1)
            {
                for(int j=0;j<n;j++)
                {
                    for(int c=0;c<n;c++)
                    {
                        if(tab[j][k].moze==true)
                            cout<<tab[j][i].quantity;
                    }
                }
                return true;
            }
            if (back(n,tab,k+1))
                return true;
            else
                tab[k][i].moze=false;
        }
    }
    return false;
}

如何修复我的函数？

---

function mark(r, c, available):
    for each element in [r][]:
        mark available
    for each element in [][c]:
        mark available
function backtrack(table, temp, r, c, sum):
    check if sum is solution
    for row i in table:
        if temp[i][0] is not available go to next row
        for column j in table:
            if temp[i][j] is available:
                 mark(i, j, not available) 
                 backtrack(table, temp, i, j, sum+table[i][j])
                 mark(i, j, available again)

我

有一个伪代码，但我不能把它放在我的函数中，有人可以帮助我，不能帮助自己

Answer 1

由于这只是一个小数组，你可以蛮力（有 4！=24 种可能性），只取最好的一个

此函数为您提供最小总和，如果您还需要选定的元素，则很容易调整代码。请注意，INF 应该很大，而 M 是给定的 4x4 数组。

int aux(){
  std::vector<int> t(4);
  for(int i=0;i<4;++i)
    t[i]=i;
  int mini=INF;
  do{
    int tmp=0;
    for(int i=0;i<4;++i)
      tmp+=M[i][t[i]];
    mini=std::min(mini, tmp);
  }while(std::next_permutation(t.begin(), t.end()));
  return mini;
}

Answer 2

目前，您的函数只返回它找到的第一个结果。

您需要，而不是您的 2 个return语句，只需记录最佳结果即可。

我不会为你编写代码，因为你会通过自己弄清楚来了解更多信息，但这里有 2 个提示可以帮助你入门：

• 您可能希望在函数外部存储最佳结果，而不是传递它。
要存储最佳结果，
• 您必须存储所选值的所有索引，而不仅仅是结果总和。

我希望这有所帮助。