Java区间拆分子集求和_java – 受限子集求和到指定范围

我有一个数组,其中只包含两种类型的数字(x和x-1),例如： – {5,5,4,4,5,5,5},我给出的范围像12-14(含).我已经知道数组的长度是常数7,我也知道数组中每种类型的元素数量(计数)

现在我需要找出数组中是否有任何元素组合,其总和落在该范围内.

我需要的是子集中的元素数量,其总和落在该范围内.

我通过以下方式使用蛮力来解决这个问题,但它非常有效.

这里count是数组中x-1的数量

for(int i=0;i<=7-count;i++){

for(int j=0;j<=count;j++){

if(x*(i)+(x-1)*j>=min && x*(i)+(x-1)*j<=max){

output1=i+j;

}

}

}

有人可以告诉我是否有更好的方法来解决这个问题

例：-

给出的数组是{5,5,4,4,5,5,5},给出的范围是12-14.

所以我会选择总和为14的{5,5,4}子集,因此子集中元素数量的答案将为3. {5,4,4}也可以在此解决方案中选取

最佳答案 您可以通过一些分析来改善您的蛮力.

N是数组长度,n是结果：

0 <= n <=N

0 <= j <= count

0 <= i <= N - count

n = i + j -> j <= n

sum = x * i + (x - 1) * j = x * n - j

min <= x * n - j <= max -> x * n - max <= j <= x * n - min

min <= x * n - j -> n >= (min + j) / x >= min / x

x * n - j <= max -> n <= (max + j) / x <= (max + count) / x

总结你可以使用你的周期,但与其他范围：

for (int n = min / x; n <= min (N, (max + count) / x); n++)

{

for (int j = max (0, x * n - max); j <= min (count, x * n - min, n); j++)

{

sum = x * n - j;

if (sum >= min && sum <= max)

{

output1 = n;

}

}

}