p*2
5 楼
不就是0-n-1的排列吗?
w*x
10 楼
一维数组record, 递归得了
i*7
16 楼
本来在想greedy的,不过后来觉得好像还是只能类似八皇后的permutation
e*l
20 楼
第一行的N个元素,分别对应N个(N-1)x(N-1)的余子阵(即去掉这个元素所在的行和列
之后剩下的矩阵)。假设N个余子阵上该问题的最优解已经得到(递归),就可以通过
比较第一行元素的N种选择,来得到NxN上的最优解。
之后剩下的矩阵)。假设N个余子阵上该问题的最优解已经得到(递归),就可以通过
比较第一行元素的N种选择,来得到NxN上的最优解。
f*e
23 楼
先用LP表示:
min sum_(ij)(w_ij*x_ij)
s.t. sum_i(x_ij)=1, sum_j(x_ij)=1, 0<=x_ij<=1
然后看能否转成combinatorial的问题。
minimum cost flow(algorithm design上有详细介绍)。
想到了,每行对应一个源s_i,每列对应一个汇t_j,
每个数组元素w_ij看成是一个node,与源s_i,汇t_j相连,
N个源s_i与总源s相连,N个汇t_j与总汇t相连,
边的cost是w_ij/2,capacity是1,其他边cost=0。
【在 t**********t 的大作中提到】
: N x N integer矩阵。
: 每一行取一个数, 且取出的每一个数必须不同列。取出N个数使得其sum最小.
: 求取法。
: 感觉应该可以用DP做?
min sum_(ij)(w_ij*x_ij)
s.t. sum_i(x_ij)=1, sum_j(x_ij)=1, 0<=x_ij<=1
然后看能否转成combinatorial的问题。
minimum cost flow(algorithm design上有详细介绍)。
想到了,每行对应一个源s_i,每列对应一个汇t_j,
每个数组元素w_ij看成是一个node,与源s_i,汇t_j相连,
N个源s_i与总源s相连,N个汇t_j与总汇t相连,
边的cost是w_ij/2,capacity是1,其他边cost=0。
【在 t**********t 的大作中提到】
: N x N integer矩阵。
: 每一行取一个数, 且取出的每一个数必须不同列。取出N个数使得其sum最小.
: 求取法。
: 感觉应该可以用DP做?
b*d
25 楼
e*l
26 楼
Interesting。
把x_ij松弛了之后,能得到一个数值解,在离散化吗?能保证全局最优吗?
【在 f*****e 的大作中提到】
: 先用LP表示:
: min sum_(ij)(w_ij*x_ij)
: s.t. sum_i(x_ij)=1, sum_j(x_ij)=1, 0<=x_ij<=1
: 然后看能否转成combinatorial的问题。
: minimum cost flow(algorithm design上有详细介绍)。
: 想到了,每行对应一个源s_i,每列对应一个汇t_j,
: 每个数组元素w_ij看成是一个node,与源s_i,汇t_j相连,
: N个源s_i与总源s相连,N个汇t_j与总汇t相连,
: 边的cost是w_ij/2,capacity是1,其他边cost=0。
把x_ij松弛了之后,能得到一个数值解,在离散化吗?能保证全局最优吗?
【在 f*****e 的大作中提到】
: 先用LP表示:
: min sum_(ij)(w_ij*x_ij)
: s.t. sum_i(x_ij)=1, sum_j(x_ij)=1, 0<=x_ij<=1
: 然后看能否转成combinatorial的问题。
: minimum cost flow(algorithm design上有详细介绍)。
: 想到了,每行对应一个源s_i,每列对应一个汇t_j,
: 每个数组元素w_ij看成是一个node,与源s_i,汇t_j相连,
: N个源s_i与总源s相连,N个汇t_j与总汇t相连,
: 边的cost是w_ij/2,capacity是1,其他边cost=0。
x*o
28 楼
求大牛鉴定,这个也N!吗?
public int findMin(int[][] a)
{
if (a == null || a.length == 0)
{
return 0;
}
if (a.length == 1)
{
return a[0][0];
}
int n = a[0].length;
ArrayList avail = new ArrayList();
for (int i = 0; i < n; i++)
{
avail.add(i);
}
return find(a, 0, avail);
}
private int find(int[][] a, int curRow, ArrayList availCols)
{
if (availCols.size() == 1)
{
return a[curRow][availCols.get(0)];
}
else
{
int min = Integer.MAX_VALUE;
for (int i : availCols)
{
int cur = a[curRow][i];
ArrayList rest = (ArrayList) availCols.
clone();
rest.remove(rest.indexOf(i));
int min_s = cur + find(a, curRow + 1, rest);
if (min_s < min)
{
min = min_s;
}
}
return min;
}
}
public int findMin(int[][] a)
{
if (a == null || a.length == 0)
{
return 0;
}
if (a.length == 1)
{
return a[0][0];
}
int n = a[0].length;
ArrayList
for (int i = 0; i < n; i++)
{
avail.add(i);
}
return find(a, 0, avail);
}
private int find(int[][] a, int curRow, ArrayList
{
if (availCols.size() == 1)
{
return a[curRow][availCols.get(0)];
}
else
{
int min = Integer.MAX_VALUE;
for (int i : availCols)
{
int cur = a[curRow][i];
ArrayList
clone();
rest.remove(rest.indexOf(i));
int min_s = cur + find(a, curRow + 1, rest);
if (min_s < min)
{
min = min_s;
}
}
return min;
}
}
w*g
30 楼
一种取法, 还是所有种类?
t*t
32 楼
N x N integer矩阵。
每一行取一个数, 且取出的每一个数必须不同列。取出N个数使得其sum最小.
求取法。
感觉应该可以用DP做?
每一行取一个数, 且取出的每一个数必须不同列。取出N个数使得其sum最小.
求取法。
感觉应该可以用DP做?
p*2
36 楼
不就是0-n-1的排列吗?
w*x
41 楼
一维数组record, 递归得了
i*7
47 楼
本来在想greedy的,不过后来觉得好像还是只能类似八皇后的permutation
e*l
51 楼
第一行的N个元素,分别对应N个(N-1)x(N-1)的余子阵(即去掉这个元素所在的行和列
之后剩下的矩阵)。假设N个余子阵上该问题的最优解已经得到(递归),就可以通过
比较第一行元素的N种选择,来得到NxN上的最优解。
之后剩下的矩阵)。假设N个余子阵上该问题的最优解已经得到(递归),就可以通过
比较第一行元素的N种选择,来得到NxN上的最优解。
f*e
54 楼
先用LP表示:
min sum_(ij)(w_ij*x_ij)
s.t. sum_i(x_ij)=1, sum_j(x_ij)=1, 0<=x_ij<=1
然后看能否转成combinatorial的问题。
minimum cost flow(algorithm design上有详细介绍)。
想到了,每行对应一个源s_i,每列对应一个汇t_j,
每个数组元素w_ij看成是一个node,与源s_i,汇t_j相连,
N个源s_i与总源s相连,N个汇t_j与总汇t相连,
边的cost是w_ij/2,capacity是1,其他边cost=0。
【在 t**********t 的大作中提到】
: N x N integer矩阵。
: 每一行取一个数, 且取出的每一个数必须不同列。取出N个数使得其sum最小.
: 求取法。
: 感觉应该可以用DP做?
min sum_(ij)(w_ij*x_ij)
s.t. sum_i(x_ij)=1, sum_j(x_ij)=1, 0<=x_ij<=1
然后看能否转成combinatorial的问题。
minimum cost flow(algorithm design上有详细介绍)。
想到了,每行对应一个源s_i,每列对应一个汇t_j,
每个数组元素w_ij看成是一个node,与源s_i,汇t_j相连,
N个源s_i与总源s相连,N个汇t_j与总汇t相连,
边的cost是w_ij/2,capacity是1,其他边cost=0。
【在 t**********t 的大作中提到】
: N x N integer矩阵。
: 每一行取一个数, 且取出的每一个数必须不同列。取出N个数使得其sum最小.
: 求取法。
: 感觉应该可以用DP做?
b*d
56 楼
e*l
57 楼
Interesting。
把x_ij松弛了之后,能得到一个数值解,在离散化吗?能保证全局最优吗?
【在 f*****e 的大作中提到】
: 先用LP表示:
: min sum_(ij)(w_ij*x_ij)
: s.t. sum_i(x_ij)=1, sum_j(x_ij)=1, 0<=x_ij<=1
: 然后看能否转成combinatorial的问题。
: minimum cost flow(algorithm design上有详细介绍)。
: 想到了,每行对应一个源s_i,每列对应一个汇t_j,
: 每个数组元素w_ij看成是一个node,与源s_i,汇t_j相连,
: N个源s_i与总源s相连,N个汇t_j与总汇t相连,
: 边的cost是w_ij/2,capacity是1,其他边cost=0。
把x_ij松弛了之后,能得到一个数值解,在离散化吗?能保证全局最优吗?
【在 f*****e 的大作中提到】
: 先用LP表示:
: min sum_(ij)(w_ij*x_ij)
: s.t. sum_i(x_ij)=1, sum_j(x_ij)=1, 0<=x_ij<=1
: 然后看能否转成combinatorial的问题。
: minimum cost flow(algorithm design上有详细介绍)。
: 想到了,每行对应一个源s_i,每列对应一个汇t_j,
: 每个数组元素w_ij看成是一个node,与源s_i,汇t_j相连,
: N个源s_i与总源s相连,N个汇t_j与总汇t相连,
: 边的cost是w_ij/2,capacity是1,其他边cost=0。
x*o
59 楼
求大牛鉴定,这个也N!吗?
public int findMin(int[][] a)
{
if (a == null || a.length == 0)
{
return 0;
}
if (a.length == 1)
{
return a[0][0];
}
int n = a[0].length;
ArrayList avail = new ArrayList();
for (int i = 0; i < n; i++)
{
avail.add(i);
}
return find(a, 0, avail);
}
private int find(int[][] a, int curRow, ArrayList availCols)
{
if (availCols.size() == 1)
{
return a[curRow][availCols.get(0)];
}
else
{
int min = Integer.MAX_VALUE;
for (int i : availCols)
{
int cur = a[curRow][i];
ArrayList rest = (ArrayList) availCols.
clone();
rest.remove(rest.indexOf(i));
int min_s = cur + find(a, curRow + 1, rest);
if (min_s < min)
{
min = min_s;
}
}
return min;
}
}
public int findMin(int[][] a)
{
if (a == null || a.length == 0)
{
return 0;
}
if (a.length == 1)
{
return a[0][0];
}
int n = a[0].length;
ArrayList
for (int i = 0; i < n; i++)
{
avail.add(i);
}
return find(a, 0, avail);
}
private int find(int[][] a, int curRow, ArrayList
{
if (availCols.size() == 1)
{
return a[curRow][availCols.get(0)];
}
else
{
int min = Integer.MAX_VALUE;
for (int i : availCols)
{
int cur = a[curRow][i];
ArrayList
clone();
rest.remove(rest.indexOf(i));
int min_s = cur + find(a, curRow + 1, rest);
if (min_s < min)
{
min = min_s;
}
}
return min;
}
}
w*g
61 楼
一种取法, 还是所有种类?
Y*f
63 楼
这道题是不是可以这样做:
1. 初始化选定N个元素A[0][0], A[1][1], A[2][2] .....
2. 对任意两个已经选定的元素A[i][j], A[k][m], 如果A[i][j] + A[k][m] > A[i][m]
+ A[k][j], 则从选定的N个元素里面删除A[i][j], A[k][m], 添加A[i][m], A[k][j]
, 重复这一步知道不存在前续条件的一对元素。
这样得到的应该是最优的,收敛已经改也比较快。
【在 t**********t 的大作中提到】
: N x N integer矩阵。
: 每一行取一个数, 且取出的每一个数必须不同列。取出N个数使得其sum最小.
: 求取法。
: 感觉应该可以用DP做?
1. 初始化选定N个元素A[0][0], A[1][1], A[2][2] .....
2. 对任意两个已经选定的元素A[i][j], A[k][m], 如果A[i][j] + A[k][m] > A[i][m]
+ A[k][j], 则从选定的N个元素里面删除A[i][j], A[k][m], 添加A[i][m], A[k][j]
, 重复这一步知道不存在前续条件的一对元素。
这样得到的应该是最优的,收敛已经改也比较快。
【在 t**********t 的大作中提到】
: N x N integer矩阵。
: 每一行取一个数, 且取出的每一个数必须不同列。取出N个数使得其sum最小.
: 求取法。
: 感觉应该可以用DP做?
Y*Y
64 楼
这个想法不错,但不能保证收敛到最优解:
比如这个:初始是{1, 1, 1},对任何两个都是最优,所以无法达到{0, 0, 0}
1 1000 0
0 1 1000
1000 0 1
m]
【在 Y********f 的大作中提到】
: 这道题是不是可以这样做:
: 1. 初始化选定N个元素A[0][0], A[1][1], A[2][2] .....
: 2. 对任意两个已经选定的元素A[i][j], A[k][m], 如果A[i][j] + A[k][m] > A[i][m]
: + A[k][j], 则从选定的N个元素里面删除A[i][j], A[k][m], 添加A[i][m], A[k][j]
: , 重复这一步知道不存在前续条件的一对元素。
: 这样得到的应该是最优的,收敛已经改也比较快。
比如这个:初始是{1, 1, 1},对任何两个都是最优,所以无法达到{0, 0, 0}
1 1000 0
0 1 1000
1000 0 1
m]
【在 Y********f 的大作中提到】
: 这道题是不是可以这样做:
: 1. 初始化选定N个元素A[0][0], A[1][1], A[2][2] .....
: 2. 对任意两个已经选定的元素A[i][j], A[k][m], 如果A[i][j] + A[k][m] > A[i][m]
: + A[k][j], 则从选定的N个元素里面删除A[i][j], A[k][m], 添加A[i][m], A[k][j]
: , 重复这一步知道不存在前续条件的一对元素。
: 这样得到的应该是最优的,收敛已经改也比较快。
x*0
65 楼
mark
m*g
66 楼
This is a NP problem.
c*t
68 楼
Y*y
72 楼
这个就是经典的one to one assignment problem吧。
l*b
73 楼
对啊, 好像就是前阵hackercup闹得那个hungarian method
G家题目真难呀,不会做...
G家题目真难呀,不会做...
j*2
76 楼
我本来想:不就是八皇后改改吗?看完大家的回帖后,我只有说:Wow!
s*t
79 楼
感觉如果N的值够小的话(e.g.<=32)是可以用dp做的。
大的话不会了: D
用一个二进制数表示取列的状态,比如S = 8 = 1000表示列0被取了,其它3列没被取
dp[i][s]表示取到第i行的时候取列状态为s时的最大值
for(int i=0; ifor(int row=1; row for(int s=0; sdp[row][s] = max( dp[row-1][s/one_digit]+data[row][this_digit], dp[row]
[s]);
}
}
这里s/one_digit代表用某一位来试一下,如果这一位已经被取,那么不取,否则就取。
data[row][this_digit]代表这个矩阵里面我们正在考虑的row行this_digit列,也就是
用来试的那一列
输出dp[N-1][(1< 复杂度N*2^N,所以只能处理小数据= =#
大的话不会了: D
用一个二进制数表示取列的状态,比如S = 8 = 1000表示列0被取了,其它3列没被取
dp[i][s]表示取到第i行的时候取列状态为s时的最大值
for(int i=0; ifor(int row=1; row
[s]);
}
}
这里s/one_digit代表用某一位来试一下,如果这一位已经被取,那么不取,否则就取。
data[row][this_digit]代表这个矩阵里面我们正在考虑的row行this_digit列,也就是
用来试的那一列
输出dp[N-1][(1<
s*t
80 楼
应该把max换成min...INF换成-INF...
我了个去的。。。这马虎程度真是一面就挂
row]
【在 s******t 的大作中提到】
: 感觉如果N的值够小的话(e.g.<=32)是可以用dp做的。
: 大的话不会了: D
: 用一个二进制数表示取列的状态,比如S = 8 = 1000表示列0被取了,其它3列没被取
: dp[i][s]表示取到第i行的时候取列状态为s时的最大值
: for(int i=0; i: for(int row=1; row : for(int s=0; s: dp[row][s] = max( dp[row-1][s/one_digit]+data[row][this_digit], dp[row]
: [s]);
: }
我了个去的。。。这马虎程度真是一面就挂
row]
【在 s******t 的大作中提到】
: 感觉如果N的值够小的话(e.g.<=32)是可以用dp做的。
: 大的话不会了: D
: 用一个二进制数表示取列的状态,比如S = 8 = 1000表示列0被取了,其它3列没被取
: dp[i][s]表示取到第i行的时候取列状态为s时的最大值
: for(int i=0; i: for(int row=1; row
: [s]);
: }
相关阅读
转CS,duplicate advanced degree的问题拿到OPT的EAD后的问题,顺便报进度提供 Google referral同一家猎头的不同recruiters 联系我for不同的positions怎么处理?Apple的芯片组(Silicon Engineering Group)内部出职位墙街插管吸血金融寄生族的暴富之道。 (转载)请教一下,申请OPT的照片可以戴眼镜吗新鲜毕业生求问,明年的H1B已满,对于今年的毕业生意味着什么?面试题M onsite借人气 问个换title的问题Java和C++的面试书籍天天被毙,可咋整啊?polymer, nano, chemistry的悲催.接受了offer可以反悔吗?有没地方既有油工又有码工机会求助:有谁知道去哪做本科学位评估的?可以不用看cc150题了灬WLT 的最新预测。 (转载)关于内存重新分配的基础问题。Startup openings in MetroDC area