# Q：n×n矩阵给出了我们必须找到

N things to select for N people, you were given a NxN matrix and cost at each element, you needed to find the one combination with max total weight, such that each person gets exactly one thing.

I found difficulty in making its dp state. please help me and if possible then also write code for it

n选择N人，你在每个单元给定一个n×n矩阵和成本，你需要找到一个结合的最大总重量，这样每个人得到一件事。

I found difficulty in making its dp state. please help me and if possible then also write code for it

C++ style code:

``````double max_rec(int n, int r, int* c, double** m, bool* f)
{
if (r < n)
{
double max_v = 0.0;
int max_i = -1;
for (int i = 0; i < n; i++)
{
if (f[i] == false)
{
f[i] = true;
double value = m[r][i] + max_rec(n, r + 1, c, m, f);
if (value > max_v)
{
max_v = value;
max_i = i;
}
f[i] = false;
}
}
c[i] = max_i;
return max_v;
}
return 0.0;
}

int* max_comb(int n, double** m)
{
bool* f = new bool[n];
int* c = new int[n];
max_rec(n, 0, c, m, f);
delete [] f;
return c;
}
``````

Call max_comb with N and your NxN matrix (2d array). Returns the column indices of the maximum combination.

Time complexity: O(N!) I know this is bad but the problem does not have a greedy structure.

And as @mszalbach said, try to attempt the problem yourself before asking.

EDIT: can reduce to polynomial time by memoizing.

C++风格的代码：

``````double max_rec(int n, int r, int* c, double** m, bool* f)
{
if (r < n)
{
double max_v = 0.0;
int max_i = -1;
for (int i = 0; i < n; i++)
{
if (f[i] == false)
{
f[i] = true;
double value = m[r][i] + max_rec(n, r + 1, c, m, f);
if (value > max_v)
{
max_v = value;
max_i = i;
}
f[i] = false;
}
}
c[i] = max_i;
return max_v;
}
return 0.0;
}

int* max_comb(int n, double** m)
{
bool* f = new bool[n];
int* c = new int[n];
max_rec(n, 0, c, m, f);
delete [] f;
return c;
}
``````

Time complexity: O(N!) I know this is bad but the problem does not have a greedy structure.

dynamic-programming