java - 限制子集总和到指定范围内

Question

我有一个数组，它只包含 2 种类型的数字(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}

Answer 1

您可以通过一些分析来提高您的蛮力。

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

P.S.:这里有一些图片可能有助于理解这个想法 graph http://i.zlowiki.ru/110917_768e5221.jpg