子集合 - 二维动态规划

我试图找到全部一组n个数字的总和为m的子集。例如，如果我有集合(10,20,30,40,40,50,80)和m = 90，子集是(10,80),(20,30,40)和(40,50)。我有代码，会发现小的情况下这样使用类似...子集合 - 二维动态规划

M[i, j] = max(M[i − 1, j], M[i − 1, j − A[i])

然后使用回溯...

if (M[n][m]!=0) 
{ 
    for (i = n; i >= 1; i --) 
     if (M[i - 1][j]!=M[i][j]) 
     { 
      printf ("Use item %d = %d\n", i, A[i]); 
      j -= A[i]; 
     } 
}

但是当我尝试更大的测试用例，它不会返回所有的子集。任何帮助将非常感激。

来源

2011-11-12 user1013032

我们怎么帮你，如果你不”告诉我们你正在使用的代码？请不要显示您项目中的所有代码，只需显示相关位。 – NickLH

首先：数字是否都是正数（或至少是非负数）？其次，你的例子包含40次两次，是一个错字还是多个元素允许的？ –

所有元素都是正数，并且允许多个元素。 – user1013032

/* first we sort M with a quicksort, for instance, 
    whose an efficient implementation can be easily found on the web. */ 
M = quicksort(M); 

/* we don't consider elements greater than m 
    so we compute the index of the greatest element to consider */ 
int max = n - 1; 
for (; max > 0 && M[max] > m; max--); 

int total = 1 << (max + 1); 
for (int i = 0; i < total; i++) 
{ 
    /* In this loop we'll go through all the possible subsets of M */ 
    int sum = 0; 
    for (int k=0; k<n; k++) 
    { 
     if ((1 << k) & i) 
     { 
      s += M[k]; 

      /* if s is greater than m no need to go further */ 
      if (s > m) 
      { 
       break; 
      } 
     } 
    } 
    if (sum == m) 
    { 
     /* Here we have found a successful subset so 
      we can output it however we want. 
      It is composed of all the elements used 
      to build s in the loop above */   
    } 
}

来源

2011-11-12 19:35:27 PierrOz

如果我们遍历所有可能的子集，那么它不会是动态编程，对吗？ – user1013032

您可以编写更动态的解决方案：对于您设置的每个元素，您都有两个选项：它是否成功。围绕这个想法，你可以为每个新的元素建立一个递归的方法来考虑，但最后它仍然会通过2^n个可能的子集，因为你想要的所有子集的总和等于m – PierrOz

@PierrOz它通常不会经过所有，因为你可以修剪（如果元素是非负的）。在这个例子中，你不需要考虑任何包含80和50的子集（修剪2 ^（n-2）子集）等。 –

所有的数字都是正值可以修剪，这大大降低了复杂度（尽管我平均不知道多少）。大集，你可能需要一个更精致的算法，但在这里有云：

排序（多）设置成一个阵列，说nums;例如，nums = {10,20,30,40,40,50,80}
创建一个累积和数组，cum;这将是暨= {10，30，60，100，140，190，270}

现在（C-ISH伪代码）

void parts(target, index, set){ // assuming we only want to print the sets out 
    if (target == 0){ 
     print out set; 
     return; 
    } 
    while(index >= 0 && nums[index] > target) --index; // skip too large numbers 
    if (index < 0 || cum[index] < target) return; // done, all numbers too large or total too small 
    for(; index >= 0 && cum[index] >= target; --index){ // we can stop when the total sum is too small 
     add nums[index] to set; 
     parts(target - nums[index], index-1, set); 
     remove nums[index] from set; 
     // if no duplicate sets are desired, skip duplicates, for the example, 
     // (40,50) would be created twice without skipping: 
     // while(index > 0 && nums[index-1] == nums[index]) --index; 
    } 
}

来源

2011-11-12 21:58:37

子集合 - 二维动态规划

回答

相关问题