最小割.
考虑如果把 A1,i 置为 1 ,就把 A×B−C 加上了 Bi 这个行向量.
最后的 D=(A×B−C)×AT ,所以最后只算那些 A1,i=1 的 (A×B−C)1,i .
设 S={i|A1,i=1} ,则 D=∑i∈S∑j∈SBi,j−∑i∈SC1,i .
意义是,若两个位置 i,j 同时被选,会带来 Bi,j 的收益,若 i 被选,需要付出 C1,i 的代价.
这显然已经是最小割经典问题了.
1 | //%std |
夢はここに 思い出は遠くに
最小割.
考虑如果把 A1,i 置为 1 ,就把 A×B−C 加上了 Bi 这个行向量.
最后的 D=(A×B−C)×AT ,所以最后只算那些 A1,i=1 的 (A×B−C)1,i .
设 S={i|A1,i=1} ,则 D=∑i∈S∑j∈SBi,j−∑i∈SC1,i .
意义是,若两个位置 i,j 同时被选,会带来 Bi,j 的收益,若 i 被选,需要付出 C1,i 的代价.
这显然已经是最小割经典问题了.
1 | //%std |
Related Issues not found
Please contact @jkloverdcoi to initialize the comment