ограниченная сумма подмножества в указанном диапазоне

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.

поэтому я бы выбрал {5,5,4} подмножество, сумма которого равна 14, и поэтому ответ на количество элементов в подмножестве будет 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;
        }
    }
}

PS: вот некоторая картина, которая может помочь понять идею graph http://i.zlowiki.ru/110917_768e5221.jpg

Answer 2

говорят, что вы хотите узнать количество a с и b с, которые добавляют к n При тестировании числа a вам нужно только использовать деление, чтобы найти число b.

т.е.

number of a * a + number of b * b = n

т.

number of b = (n - number of a * a) / b;

РЕДАКТИРОВАТЬ: Если это число является целым числом, у вас есть решение.

Чтобы проверить, является ли делениецелое число, которое вы можете сделать

(`n` - `number of a` * `a`) % `b` == 0

, если у вас разброс диапазона меньше b, вы можете сделать

(`min` - `number of a` * `a`) % `b` <= `max` - `min`

, если спрэд больше или равен b у вас всегда есть ряд решений.

Я предполагаю, что b положительно.