在不使用递归的情况下针对顺序范围改进此子集求和算法
Improving this subset sum algorithm for a sequential range without using recursion
给定一个 min & max 我想使用指定数量的 [=16] 找到该范围内加起来等于给定 total 的所有数字组合=]（重复使用数字是可以的）。 # of bins 将接近但不超过 32，所以如果这是一个选项，按位是很棒的。
例如：
input:
min = 1
max = 4
total = 9
bins = 4
output:
1,1,3,4
1,2,2,4
1,2,3,3
2,2,2,3
我蹩脚、低效的解决方案：
function arrSum(arr) {
var sum = 0;
for (var i = 0; i < arr.length; i++) {
sum += arr[i];
}
return sum;
}
function incrementComboArr(arr, maxNum) {
var i = arr.length - 1;
while (i >= 0) {
if (++arr[i] > maxNum) {
i--;
} else {
for (var j = i + 1; j < arr.length; j++) {
arr[j] = arr[i];
}
break;
}
}
return i === -1;
}
getSetCombos = function (minNum, maxNum, target, bins) {
var iters = 0;
var solutions = [];
var arr = [];
var i;
for (i = 0; i < bins; i++) {
arr[i] = minNum;
}
while (true) {
iters++;
var sum = arrSum(arr);
if (sum === target) {
solutions.push(arr.slice());
}
if (incrementComboArr(arr, maxNum)) break;
}
console.log(iters);
return solutions;
};
我的解决方案的问题在于，即使当前迭代与目标值之间的增量是确定性的，它也会增加 1。而且，它不知道什么时候停止。 （我可以通过做 if arr[0] > ~~(total/bins) 之类的事情来确定最后一个可行的解决方案，但这看起来很奇怪。鉴于该系列是一个序列，我知道必须有一些我没有利用的模式，但我可以'没想到。Code/ideas/lecture欢迎大家留言！
结果
将两个答案都转换为 ES5 后（欢迎编辑），第一个解决方案的时间约为 5 毫秒，第二个（递归）约为 500 毫秒。我会在一天内将其标记为已回答。
这是我为每个使用的代码：
//Code translated from Spektre
subsetSum = function (minNum, maxNum, target, bins) {
var start = new Date();
var solutions = [];
var arr = [];
var i;
var s;
var loop = true;
for (i = 0; i < bins; i++) {
arr[i] = minNum;
}
s = minNum * bins;
while (loop) {
if (s === target) {
solutions.push(arr.slice());
}
for (i = bins;;) {
i--;
arr[i]++;
s++;
for (var j = i + 1; j < bins; j++) {
s+= arr[i]-arr[j];
arr[j]=arr[i];
}
if ((s<=target)&&(arr[i]<=maxNum)) break;
if (!i) {
loop = false;
break;
}
s+=maxNum-arr[i];
arr[i]=maxNum;
}
}
return new Date() - start;
};
//Code translated from karthik
subsetSumRecursive = function(minNum, maxNum, target, bins) {
var start = new Date();
var solutions = [];
var arr= [], i;
var totalBins = bins;
for (i = 0; i < bins; i++) {
arr[i] = minNum;
}
target -= minNum * bins;
countWays(target, bins, arr, 0);
return new Date() - start;
function countWays(target, binsLeft, arr) {
if (binsLeft === 1) {
arr[totalBins-1] += target;
if (arr[totalBins-1] <= maxNum) {
solutions.push(arr.slice());
}
return;
}
if (target === 0 && arr[totalBins-binsLeft] <= maxNum) {
solutions.push(arr.slice());
return;
}
var binsCovered = 0;
if (target >= binsLeft) {
var newArr = arr.slice();
while (binsCovered < binsLeft) {
newArr[totalBins - binsCovered -1]++;
binsCovered++;
}
countWays(target - binsLeft, binsLeft, newArr);
}
countWays(target, binsLeft-1, arr);
}
};
subsetSum(1,4,100,32);
subsetSumRecursive(1,4,100,32);
在 C++ 中我会这样做：
//---------------------------------------------------------------------------
AnsiString subset_sum(int min,int max,int sum,int N)
{
AnsiString txt="",lin; int cnt=0; // output text and number of subsets fond
int i,s,a[32]; // iterator,actual sum,actual permutation
// init nested for
for (i=0;i<N;i++) a[i]=min; s=min*N;
// nested for
for (bool _loop=true;_loop;)
{
// if correct sum remember it to txt and update cnt
if (s==sum)
{
for (lin="",i=0;i<N;i++) lin+=AnsiString(a[i])+" "; txt+=lin+"\r\n";
cnt++;
}
// nested for step lequeal
for (i=N;;)
{
i--; a[i]++; s++;
if ((s<=sum)&&(a[i]<=max)) break;
if (!i) { _loop=false; break; }
s-=a[i]; a[i]=min; s+=a[i];
}
}
txt+=AnsiString(cnt)+" subsets found\r\n";
return txt;
}
//---------------------------------------------------------------------------
- 基于nested for in C++
- 并添加条件以忽略更高的总和
- 可以通过计算最后一个
a[N-1]=sum-s 来加快速度
- 对于 32 个垃圾箱，这也太慢了吗...
- 但比你的方法快得多
[edit1] 删除（位置洗牌）重复项
//---------------------------------------------------------------------------
AnsiString subset_sum(int min,int max,int sum,int N)
{
AnsiString txt="",lin; int cnt=0; // output text and number of subsets fond
int i,j,s,a[32]; // iterator,actual sum,actual permutation
// init nested for
for (i=0;i<N;i++) a[i]=min; s=min*N;
// nested for
for (bool _loop=true;_loop;)
{
// if correct sum remember it to txt and update cnt
if (s==sum)
{
for (lin="",i=0;i<N;i++) lin+=AnsiString(a[i])+" "; txt+=lin+"\r\n";
cnt++;
}
// nested for step lequeal
for (i=N;;)
{
i--; a[i]++; s++;
for (j=i+1;j<N;j++) { s+=a[i]-a[j]; a[j]=a[i]; }
if ((s<=sum)&&(a[i]<=max)) break;
if (!i) { _loop=false; break; }
s+=max-a[i]; a[i]=max;
}
}
txt+=AnsiString(cnt)+" subsets found\r\n";
return txt;
}
//---------------------------------------------------------------------------
现在增量是这样的：
1,1,1,1
1,1,1,2
1,1,1,3
1,1,1,4
1,1,2,2
1,1,2,3
1,1,2,4
1,1,3,3
...
subset_sum(1,4,100,32);
的速度现在非常棒，只有短短的 5.4 [ms]
这里是结果：
1 1 1 1 1 1 1 1 1 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 1 1 1 1 1 2 2 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 1 1 1 1 1 2 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 1 1 1 1 1 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 1 1 1 1 2 2 2 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 1 1 1 1 2 2 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 1 1 1 1 2 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 1 1 1 1 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 1 1 1 2 2 2 2 2 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 1 1 1 2 2 2 2 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 1 1 1 2 2 2 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 1 1 1 2 2 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 1 1 1 2 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 1 1 1 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 1 1 2 2 2 2 2 2 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 1 1 2 2 2 2 2 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 1 1 2 2 2 2 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 1 1 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 1 1 2 2 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 1 1 2 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 1 1 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 1 2 2 2 2 2 2 2 2 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 1 2 2 2 2 2 2 2 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 1 2 2 2 2 2 2 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 1 2 2 2 2 2 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 1 2 2 2 2 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 1 2 2 2 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 1 2 2 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 1 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 1 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 2 2 2 2 2 2 2 2 2 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 2 2 2 2 2 2 2 2 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 2 2 2 2 2 2 2 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4
1 1 1 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4
1 1 2 2 2 2 2 2 2 2 2 2 2 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 2 2 2 2 2 2 2 2 2 2 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4
1 1 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4
1 1 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4
1 1 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4
1 1 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4
1 2 2 2 2 2 2 2 2 2 2 2 2 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 2 2 2 2 2 2 2 2 2 2 2 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4
1 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4
1 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4
1 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4
1 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4
1 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4
1 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4
1 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4
2 2 2 2 2 2 2 2 2 2 2 2 2 2 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4
2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4
2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4
2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4
2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4
2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4
2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4
2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4
2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4
2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4
80 subsets found
它可能看起来很复杂，但是一旦你理解了为什么按升序排列东西可以避免重复，它就很容易了:)
我试图通过你的解决方案，但无法完全理解它。
我将从递归开始，我知道您不需要递归解决方案，但这是一个动态规划递归，因此很容易将其转换为迭代解决方案。
你没有给 total 起名字，所以说你必须在 k 个礼品盒中分发 n 巧克力，所以礼品盒的数量 = k & 总数= n 并且为了简单起见 arr= {min,min+1, .....max} 是一个数组。
现在避免重复的关键是按升序分配巧克力（降序也可以）。所以你7颗巧克力，我在第一个盒子里放2个巧克力，我至少会在第二个盒子里放2。为什么？这有助于避免重复。
you will have to use base cases like n>0 , number of items < max
now onwards TCL = totalChocholatesLeft & TBL = totalBinsLeft
So S(TCL,TBL) = S(TCL-TBL,TBL) + S(TCL,TBL-1);
you have to call the above expression starting with S(n-(k*min), k)
Why? because all boxes need at least one item so first put `min` each box.
Now you are left with only n-(k*min) chocolates.
就是这样！这就是 DP 递归。
它是如何工作的？
So in order to remove repetitions we are maintaning the ascending order.
What is the easiest way to maintain the ascending order ?
如果你在第i个盒子里放了1个巧克力，那么在它前面的所有盒子里都放1个i+1, i++2 .....k。
所以把巧克力放在礼盒里之后，你有两个选择:
是否要继续当前框：
S(TCL-TBL,TBL) covers this
或者移动下一个框只是不再考虑这个框
S(TCL,TBL-1) covers this.
如果你想更容易维护最大约束，你可以传递一个List<Integer>代表每个bin中元素的数量。
因此，在调用递归之前，您必须将每个 bin 中的元素数量增加 1。这将使 TC ：O(N^2K)
这是一个有效的代码：我刚刚编写了递归函数，您可以使用输出[n][k] 数组并将其转换为 DP，只要有函数调用（countWays(x,y)) 只需检查 countWays[x][y] 是否为 -1 然后仅递归调用该函数否则仅 return 值
static int totalWays = 0;
static int totalbins=32,bins=32;
static int min=1,max=4;
static int[][] countWays;
public static void main(String[] args) throws IOException {
int[] chocs = new int[bins];
int total = 100;
for(int i=0;i<bins;i++){
chocs[i] =min;
}
countWays= new int[total+1][bins+1];
for(int i=1;i<total+1;i++){
for(int j=1;j<bins+1;j++){
countWays[i][j]= -1;
}
}
total = total - (min*bins);
countWays[total][bins] =countWays(total,bins,chocs);
System.out.println("Total ways:" + totalWays);
System.out.println("Total ways:" + countWays[total][bins]);
}
private static int countWays(int total, int binsLeft, int[] chocs) {
if(binsLeft == 1){
chocs[totalbins-1]= chocs[totalbins-1] +total;
if(chocs[totalbins-1] <= max) {
doStuff(chocs);
return 1;
}
countWays[total][1]=0;
return 0;
}
if(total == 0 ){
if(chocs[totalbins-binsLeft] <= max) {
doStuff(chocs);
return 1;
}else{
return 0;
}
}
int binsCovered =0;
int x=0,y=0;
if(total >= binsLeft) {
int[] newArray = new int[totalbins];
for (int i = 0; i < totalbins; i++) {
newArray[i] = chocs[i];
}
while (binsCovered < binsLeft) {
newArray[totalbins - binsCovered - 1]++;
binsCovered++;
}
x = countWays(total - binsLeft, binsLeft, newArray);
}
y = countWays(total, binsLeft-1, chocs);
countWays[total][binsLeft] = x+y;
return countWays[total][binsLeft];
}
public static void doStuff(int[] chocs) {
totalWays++;
// for(int i=0;i<totalbins;i++)
// {
// // System.out.print(chocs[i] + " ");
// }
// //System.out.println();
}
给定一个 min & max 我想使用指定数量的 [=16] 找到该范围内加起来等于给定 total 的所有数字组合=]（重复使用数字是可以的）。 # of bins 将接近但不超过 32，所以如果这是一个选项，按位是很棒的。
例如：
input:
min = 1
max = 4
total = 9
bins = 4
output:
1,1,3,4
1,2,2,4
1,2,3,3
2,2,2,3
我蹩脚、低效的解决方案：
function arrSum(arr) {
var sum = 0;
for (var i = 0; i < arr.length; i++) {
sum += arr[i];
}
return sum;
}
function incrementComboArr(arr, maxNum) {
var i = arr.length - 1;
while (i >= 0) {
if (++arr[i] > maxNum) {
i--;
} else {
for (var j = i + 1; j < arr.length; j++) {
arr[j] = arr[i];
}
break;
}
}
return i === -1;
}
getSetCombos = function (minNum, maxNum, target, bins) {
var iters = 0;
var solutions = [];
var arr = [];
var i;
for (i = 0; i < bins; i++) {
arr[i] = minNum;
}
while (true) {
iters++;
var sum = arrSum(arr);
if (sum === target) {
solutions.push(arr.slice());
}
if (incrementComboArr(arr, maxNum)) break;
}
console.log(iters);
return solutions;
};
我的解决方案的问题在于，即使当前迭代与目标值之间的增量是确定性的，它也会增加 1。而且，它不知道什么时候停止。 （我可以通过做 if arr[0] > ~~(total/bins) 之类的事情来确定最后一个可行的解决方案，但这看起来很奇怪。鉴于该系列是一个序列，我知道必须有一些我没有利用的模式，但我可以'没想到。Code/ideas/lecture欢迎大家留言！
结果
将两个答案都转换为 ES5 后（欢迎编辑），第一个解决方案的时间约为 5 毫秒，第二个（递归）约为 500 毫秒。我会在一天内将其标记为已回答。
这是我为每个使用的代码：
//Code translated from Spektre
subsetSum = function (minNum, maxNum, target, bins) {
var start = new Date();
var solutions = [];
var arr = [];
var i;
var s;
var loop = true;
for (i = 0; i < bins; i++) {
arr[i] = minNum;
}
s = minNum * bins;
while (loop) {
if (s === target) {
solutions.push(arr.slice());
}
for (i = bins;;) {
i--;
arr[i]++;
s++;
for (var j = i + 1; j < bins; j++) {
s+= arr[i]-arr[j];
arr[j]=arr[i];
}
if ((s<=target)&&(arr[i]<=maxNum)) break;
if (!i) {
loop = false;
break;
}
s+=maxNum-arr[i];
arr[i]=maxNum;
}
}
return new Date() - start;
};
//Code translated from karthik
subsetSumRecursive = function(minNum, maxNum, target, bins) {
var start = new Date();
var solutions = [];
var arr= [], i;
var totalBins = bins;
for (i = 0; i < bins; i++) {
arr[i] = minNum;
}
target -= minNum * bins;
countWays(target, bins, arr, 0);
return new Date() - start;
function countWays(target, binsLeft, arr) {
if (binsLeft === 1) {
arr[totalBins-1] += target;
if (arr[totalBins-1] <= maxNum) {
solutions.push(arr.slice());
}
return;
}
if (target === 0 && arr[totalBins-binsLeft] <= maxNum) {
solutions.push(arr.slice());
return;
}
var binsCovered = 0;
if (target >= binsLeft) {
var newArr = arr.slice();
while (binsCovered < binsLeft) {
newArr[totalBins - binsCovered -1]++;
binsCovered++;
}
countWays(target - binsLeft, binsLeft, newArr);
}
countWays(target, binsLeft-1, arr);
}
};
subsetSum(1,4,100,32);
subsetSumRecursive(1,4,100,32);
在 C++ 中我会这样做：
//---------------------------------------------------------------------------
AnsiString subset_sum(int min,int max,int sum,int N)
{
AnsiString txt="",lin; int cnt=0; // output text and number of subsets fond
int i,s,a[32]; // iterator,actual sum,actual permutation
// init nested for
for (i=0;i<N;i++) a[i]=min; s=min*N;
// nested for
for (bool _loop=true;_loop;)
{
// if correct sum remember it to txt and update cnt
if (s==sum)
{
for (lin="",i=0;i<N;i++) lin+=AnsiString(a[i])+" "; txt+=lin+"\r\n";
cnt++;
}
// nested for step lequeal
for (i=N;;)
{
i--; a[i]++; s++;
if ((s<=sum)&&(a[i]<=max)) break;
if (!i) { _loop=false; break; }
s-=a[i]; a[i]=min; s+=a[i];
}
}
txt+=AnsiString(cnt)+" subsets found\r\n";
return txt;
}
//---------------------------------------------------------------------------
- 基于nested for in C++
- 并添加条件以忽略更高的总和
- 可以通过计算最后一个
a[N-1]=sum-s 来加快速度
- 对于 32 个垃圾箱，这也太慢了吗...
- 但比你的方法快得多
[edit1] 删除（位置洗牌）重复项
//---------------------------------------------------------------------------
AnsiString subset_sum(int min,int max,int sum,int N)
{
AnsiString txt="",lin; int cnt=0; // output text and number of subsets fond
int i,j,s,a[32]; // iterator,actual sum,actual permutation
// init nested for
for (i=0;i<N;i++) a[i]=min; s=min*N;
// nested for
for (bool _loop=true;_loop;)
{
// if correct sum remember it to txt and update cnt
if (s==sum)
{
for (lin="",i=0;i<N;i++) lin+=AnsiString(a[i])+" "; txt+=lin+"\r\n";
cnt++;
}
// nested for step lequeal
for (i=N;;)
{
i--; a[i]++; s++;
for (j=i+1;j<N;j++) { s+=a[i]-a[j]; a[j]=a[i]; }
if ((s<=sum)&&(a[i]<=max)) break;
if (!i) { _loop=false; break; }
s+=max-a[i]; a[i]=max;
}
}
txt+=AnsiString(cnt)+" subsets found\r\n";
return txt;
}
//---------------------------------------------------------------------------
现在增量是这样的：
1,1,1,1
1,1,1,2
1,1,1,3
1,1,1,4
1,1,2,2
1,1,2,3
1,1,2,4
1,1,3,3
...
subset_sum(1,4,100,32);
这里是结果：
1 1 1 1 1 1 1 1 1 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 1 1 1 1 1 2 2 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 1 1 1 1 1 2 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 1 1 1 1 1 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 1 1 1 1 2 2 2 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 1 1 1 1 2 2 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 1 1 1 1 2 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 1 1 1 1 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 1 1 1 2 2 2 2 2 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 1 1 1 2 2 2 2 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 1 1 1 2 2 2 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 1 1 1 2 2 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 1 1 1 2 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 1 1 1 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 1 1 2 2 2 2 2 2 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 1 1 2 2 2 2 2 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 1 1 2 2 2 2 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 1 1 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 1 1 2 2 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 1 1 2 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 1 1 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 1 2 2 2 2 2 2 2 2 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 1 2 2 2 2 2 2 2 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 1 2 2 2 2 2 2 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 1 2 2 2 2 2 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 1 2 2 2 2 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 1 2 2 2 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 1 2 2 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 1 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 1 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 2 2 2 2 2 2 2 2 2 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 2 2 2 2 2 2 2 2 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 2 2 2 2 2 2 2 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4
1 1 1 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4
1 1 1 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4
1 1 2 2 2 2 2 2 2 2 2 2 2 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 2 2 2 2 2 2 2 2 2 2 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4
1 1 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4
1 1 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4
1 1 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4
1 1 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4
1 1 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4
1 2 2 2 2 2 2 2 2 2 2 2 2 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 2 2 2 2 2 2 2 2 2 2 2 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4
1 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4
1 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4
1 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4
1 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4
1 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4
1 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4
1 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4
1 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4
2 2 2 2 2 2 2 2 2 2 2 2 2 2 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4
2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4
2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4
2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4
2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4
2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4
2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4
2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4
2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4
2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4
80 subsets found
它可能看起来很复杂，但是一旦你理解了为什么按升序排列东西可以避免重复，它就很容易了:)
我试图通过你的解决方案，但无法完全理解它。
我将从递归开始，我知道您不需要递归解决方案，但这是一个动态规划递归，因此很容易将其转换为迭代解决方案。
你没有给 total 起名字，所以说你必须在 k 个礼品盒中分发 n 巧克力，所以礼品盒的数量 = k & 总数= n 并且为了简单起见 arr= {min,min+1, .....max} 是一个数组。
现在避免重复的关键是按升序分配巧克力（降序也可以）。所以你7颗巧克力，我在第一个盒子里放2个巧克力，我至少会在第二个盒子里放2。为什么？这有助于避免重复。
you will have to use base cases like n>0 , number of items < max
now onwards TCL = totalChocholatesLeft & TBL = totalBinsLeft
So S(TCL,TBL) = S(TCL-TBL,TBL) + S(TCL,TBL-1);
you have to call the above expression starting with S(n-(k*min), k)
Why? because all boxes need at least one item so first put `min` each box.
Now you are left with only n-(k*min) chocolates.
就是这样！这就是 DP 递归。
它是如何工作的？
So in order to remove repetitions we are maintaning the ascending order.
What is the easiest way to maintain the ascending order ?
如果你在第i个盒子里放了1个巧克力，那么在它前面的所有盒子里都放1个i+1, i++2 .....k。
所以把巧克力放在礼盒里之后，你有两个选择:
是否要继续当前框：
S(TCL-TBL,TBL) covers this
或者移动下一个框只是不再考虑这个框
S(TCL,TBL-1) covers this.
如果你想更容易维护最大约束，你可以传递一个List<Integer>代表每个bin中元素的数量。
因此，在调用递归之前，您必须将每个 bin 中的元素数量增加 1。这将使 TC ：O(N^2K)
这是一个有效的代码：我刚刚编写了递归函数，您可以使用输出[n][k] 数组并将其转换为 DP，只要有函数调用（countWays(x,y)) 只需检查 countWays[x][y] 是否为 -1 然后仅递归调用该函数否则仅 return 值
static int totalWays = 0;
static int totalbins=32,bins=32;
static int min=1,max=4;
static int[][] countWays;
public static void main(String[] args) throws IOException {
int[] chocs = new int[bins];
int total = 100;
for(int i=0;i<bins;i++){
chocs[i] =min;
}
countWays= new int[total+1][bins+1];
for(int i=1;i<total+1;i++){
for(int j=1;j<bins+1;j++){
countWays[i][j]= -1;
}
}
total = total - (min*bins);
countWays[total][bins] =countWays(total,bins,chocs);
System.out.println("Total ways:" + totalWays);
System.out.println("Total ways:" + countWays[total][bins]);
}
private static int countWays(int total, int binsLeft, int[] chocs) {
if(binsLeft == 1){
chocs[totalbins-1]= chocs[totalbins-1] +total;
if(chocs[totalbins-1] <= max) {
doStuff(chocs);
return 1;
}
countWays[total][1]=0;
return 0;
}
if(total == 0 ){
if(chocs[totalbins-binsLeft] <= max) {
doStuff(chocs);
return 1;
}else{
return 0;
}
}
int binsCovered =0;
int x=0,y=0;
if(total >= binsLeft) {
int[] newArray = new int[totalbins];
for (int i = 0; i < totalbins; i++) {
newArray[i] = chocs[i];
}
while (binsCovered < binsLeft) {
newArray[totalbins - binsCovered - 1]++;
binsCovered++;
}
x = countWays(total - binsLeft, binsLeft, newArray);
}
y = countWays(total, binsLeft-1, chocs);
countWays[total][binsLeft] = x+y;
return countWays[total][binsLeft];
}
public static void doStuff(int[] chocs) {
totalWays++;
// for(int i=0;i<totalbins;i++)
// {
// // System.out.print(chocs[i] + " ");
// }
// //System.out.println();
}