0

例如，有一个 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)

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

4

2 回答 2

0

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

你需要，而不是你的 2 个return陈述，只记录你去的最佳结果。

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

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

我希望这会有所帮助。

于 2013-10-17T16:18:54.317 回答
0

由于这只是一个小数组，因此您可以蛮力（有 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;
}
于 2013-10-17T15:00:23.630 回答