什么是最小的列和区别？ [英] What's the minimal column sums difference?

问题描述

设想你给定的正整数的矩阵（最大25 * 15，数值不超过300万）。当你做列款项，并挑选最小和最大的一个，它们之间的差别必须是最小的。

Imagine you are given a matrix of positive integer numbers (maximum 25*15, value of number does not exceed 3000000). When you do column sums and pick the smallest and the largest one, the difference between them must be the smallest possible.

您可以交换每一行的数字（置换行），而不是在列，你想多少次了。

You can swap numbers in every row (permute rows), not in column, how many times you want.

你将如何解决这个任务？

How would you solve this task?

我不要求你的code，但你的想法。

I'm not asking for your code but your ideas.

在此先感谢

推荐答案

我会做一个试图解决使用模拟退火问题。这是该计划的一个素描：

I would make an attempt to solve the problem using Simulated Annealing. Here is a sketch of the plan:

1. 让的距离，以优化最大和最小列总和之间的差。
2. 设置的目标为0（即，尽量达到尽可能接近到一个矩阵和之间没有区别）
3. 通过计算所有列的总和的阵列其当前值初始化的问题。
4. 让一个的邻的当前矩阵的是导致从交换矩阵的同一行中的两个条目的矩阵。
5. 重新present邻居他们的行索引和两个交换列索引。
6. 在接受邻居，不要再计算所有款项。只需调整和的数组中已换列和增调剂（这可以从换行索引推断）
的区别

1. Let the distance to optimize the difference between the max and min column sums.
2. Set the goal to be 0 (i.e., try to reach as close as possible to a matrix with no difference between sums)
3. Initialize the problem by calculating the array of sums of all columns to their current value.
4. Let a neighbor of the current matrix be the matrix that results from swapping two entries in the same row of the matrix.
5. Represent neighbors by their row index and two swapping column indexes.
6. When accepting a neighbor, do not compute all sums again. Just adjust the array of sums in the columns that have been swapped and by the difference of the swap (which you can deduce from the swapped row index)

第六步是性能（大型矩阵）的缘故是必不可少的。

Step 6 is essential for the sake of performance (large matrices).

这篇关于什么是最小的列和区别？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！