Длина решения суммы подмножества

Я использую следующую логику для решения проблемы суммы подмножества, как описано в этом вопросе: Total сумма из множества (логика). Он работает и каждый раз дает мне одно случайное решение, проблема в том, что мне нужны только решения с определенным количеством элементов. Например:

[2,3,4,6,3] //Set of values
SUM = 6

Текущие решения, которые я могу получить:

[4,2]
[6]
[3,3]

Но что, если мне нужно, чтобы этот метод случайным образом возвращал только решение с (например) 2 элементами?


logic dynamic-programming np-complete
person mtet88    schedule 10.04.2015    source источник

Ответы (1)


arrow_upward
1
arrow_downward

На всякий случай, если это кому-то понадобится, я наконец нашел финальную модификацию.

Как предлагается в этом сообщении, матрица (или, в данном случае, куб) необходимо заполнить этой логикой:

D(x,i,j) = 0 when x<0 || j<0
D(0,i,0) = 1
D(x,0,j) = 0 when x>0 && j>0 
D(x,i,j) = D(x-arr[i],i-1,j-1) + D(x,i-1,j)

Вот формула в Obj-C, которая находит одно случайное решение с точным количеством элементов:

- (NSArray *)getSubset
{
  NSMutableArray *solution = [[NSMutableArray alloc] init];
  int i = (int) self.vals.count; //vals is the array with the values
  int j = (int) self.size; //size is the amount of values I want
  int x = (int) self.sum; //the objective sum

  //the last position has the solutions count
  if ([self.matrix[x][i][j] intValue] < 1) {
    NSLog(@"No matrix solution");
    return nil;
  }

  while (x>0) {

    NSMutableArray *possibleVals = [[NSMutableArray alloc] init];

    if ([self.matrix[x][i-1][j] intValue] > 0) {
      [possibleVals addObject:[NSNumber numberWithInt:x]];
    }

    int posR = x - [self.vals[i-1] intValue];

    if ((posR >= 0) && ([self.matrix[posR][i-1][j-1] intValue] > 0)) {
      [possibleVals addObject:[NSNumber numberWithInt:posR]];
    }

    int rand = arc4random();
    int rIndex = rand % possibleVals.count;
    int r = [possibleVals[rIndex] intValue];

    if (r != x) {
      [solution addObject:[NSNumber numberWithInt:x-r]];
      j--; //We only move through j when we've added a value
    }

    x = r;
    i--;
  }

  return solution;
}

Ваше здоровье :)

person mtet88    schedule 15.04.2015