算法是固定的.

我有一个类似的问题，我想尽量减少解决方案中不同值的数量.以下是我如何得出数学上计算不同项目数的答案.

I had a similar issue that I wanted to minimize the number of distinct values in a solution. The following is how I came up with the answer to mathematically calculate the number of distinct items.

假设我们有以下设置:

11 12 13 11 11

我们可以看到其中有3个不同的数字(11、12和13).以下是计算它的方法. 像这样将数字写在三角形矩阵中:

We can see there are 3 distinct numbers in there (11, 12, and 13). Following is the way to compute it. Write the numbers in triangle matrix like this:

11 12 13 11 11    row=0
   12 13 11 11    row=1
      13 11 11    row=2
         11 11    row=3

如果我得到11和12之差，并为

if I get the difference of 11 and 12 and assign a binary variable to

1，如果| a1-a2 | ！= 0

1 if |a1 - a2| != 0

0 == 0

然后我有以下内容:

1 1 0 0   --> 0
  1 1 1   --> 1
    1 1   --> 1
      0   --> 0

1 + 1 + (extra 1) = 3

如果数字是不同的，则其行应全为1. 因此，对于上述情况，我们有2个全1的行，这意味着我们有2个与第一个数字不同的数字.因此，总共有3个.

if a number is distinct then its row should be all 1s. So for the above case we have 2 rows of full 1s, meaning we have 2 numbers that are distinct from the first number. So, in total we have 3.

现在可以翻译成线性编程了:

Now to translate into Linear Programming:

假设:

Variables = a(1), a(2), a(3), a(4), ..., a(n)
Binary Variables b(i,j) where i,j in [0...n]
Binary Variable c(i) where i in [0...n]

线性程序为:

obj = 1
for i in range(0, n):
  for j in range(i+1, n):
    # This is |a(i) - a(j)| part
    addConstr( b(i,j) * BigM >= a(i) - a(j)) 
    addConstr( b(i,j) * BigM >= -(a(i) - a(j)))
  # So here c(i) will be 0 if there is any 0 in the row otherwise it is 1.
  addConstr(c(i) * BigM >= sum(b(i,j) for all j) - (n-i))
  obj = obj + c(i)
Minimize(Sum(obj))