子集总和解长度 [英] Subset sum solution length

问题描述

我正在使用以下逻辑来解决此问题中所述的子集和问题:

I'm using the following logic to solve the subset sum problem as described in this question: Total sum from a set (logic). It is working and it will give me one random solution every time, the problem is that I need only the solutions with an specific amount of items. For example:

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

我可以得到的当前解决方案是:

The current solutions I can get are:

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

但是，如果我需要此方法来随机返回仅包含(例如)2个项目的解决方案，该怎么办?

But what if I need this method to randomly return only a solution with (for example) 2 items?

推荐答案

以防万一有人需要它，我终于找到了最终的修改.

Just in case somebody needs this, i finally found the final modification.

如该 post 矩阵中所建议的(或在这种情况下，立方体)需要填充以下逻辑:

As suggested in this post the matrix (or in this case, the cube) needs to be filled with this logic:

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中的公式，该公式可以找到一个具有确切元素数量的随机解:

Here's the formula in Obj-C that finds one random solution with the exact amount of elements:

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

干杯:)

这篇关于子集总和解长度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！