子集和解长度

Question

我正在使用以下逻辑来解决此问题中所述的子集求和问题：。它正在工作，每次都会给我一个随机解决方案，问题是我只需要具有特定数量项目的解决方案。例如：

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

目前我能得到的方案是：

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

但是，如果我需要此方法来随机 return 仅具有（例如）2 个项目的解决方案怎么办？

Answer 1

以防万一有人需要这个，我终于找到了最终的修改。

按照此中的建议，矩阵（或在本例中为立方体）需要用以下逻辑填充：

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;
}

干杯 :)

子集和解长度

Subset sum solution length

logic

np-complete

dynamic-programming