算法进行分区/分布在所有独特的方式桶之间总和 [英] Algorithm to partition/distribute sum between buckets in all unique ways

问题描述

我需要一个算法，做这样的：

I need an algorithm that does this:

找到所有的独特的方式跨越'水桶'不关心顺序

Find all the unique ways to partition a given sum across 'buckets' not caring about order

我希望我是明确合理连贯的EX pressing自己。

I hope I was clear reasonably coherent in expressing myself.

有关的总和5和3桶，什么算法应该返回是：

For the sum 5 and 3 buckets, what the algorithm should return is:

[5，0,0]
  [4，1,0]
  [3,2，0]
  [3,1，1]   [2，2,1]

[5, 0, 0]
[4, 1, 0]
[3, 2, 0]
[3, 1, 1] [2, 2, 1]

我很抱歉，如果这个问题可能是一个傻瓜，但我不知道到底是什么，这些类型的问题被调用。不过，我搜索谷歌和SO使用我能想到的所有的字眼，但只找到结果最分配的甚至的办法，不是所有的独特的方式。

Disclaimer

I'm sorry if this question might be a dupe, but I don't know exactly what these sort of problems are called. Still, I searched on Google and SO using all wordings that I could think of, but only found results for distributing in the most even way, not all unique ways.

推荐答案

它更容易一点对我来说，code几行比写在算法5页的文章。 最简单的版本认​​为：

Its bit easier for me to code few lines than writing a 5-page essay on algorithm. The simplest version to think of:

vector<int> ans;

void solve(int amount, int buckets, int max){
  if(amount <= 0) { printAnswer(); return;}
  if(amount > buckets * max) return; // we wont be able to fulfill this request anymore

  for(int i = max; i >= 1; i--){
    ans.push_back(i);
    solve(amount-i, buckets-1, i);
    ans.pop_back();
  } 
}

void printAnswer(){
  for(int i = 0; i < ans.size(); i++) printf("%d ", ans[i]);
  for(int i = 0; i < all_my_buckets - ans.size(); i++) printf("0 ");
  printf("\n");
}

它也值得改进的地方你一叠您的选择，如点解（金额-K *我，水桶-K，I-1） - 所以你不会创造过深复发。 （据我所知堆将是大小O（开方（N））即可。

Its also worth improving to the point where you stack your choices like solve( amount-k*i, buckets-k, i-1) - so you wont create too deep recurrence. (As far as I know the stack would be of size O(sqrt(n)) then.

为什么没有动态规划？

我们不希望看到所有这些可能性计数，所以即使我们再次到达同一个点上，我们无论如何都会打印每单号，所以复杂度将保持不变。

We dont want to find count of all those possibilities, so even if we reach the same point again, we would have to print every single number anyway, so the complexity will stay the same.

我希望它可以帮助你一下，随时问我任何问题。

I hope it helps you a bit, feel free to ask me any question

这篇关于算法进行分区/分布在所有独特的方式桶之间总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！