Особый алгоритм перебора всех подмножеств мультимножества

[mustitz]

Ну.. дык можно алгоритм один в один перевести в код, там 5 секунд дела:

Используется синтаксис C

#include <stdio.h>

#define n 5
#define N 7

int w[n] = { 1, 2, 3, 4, 5 };

int c[n+1];

int delta[n+1];

void visit(const int t, const int * const c, const int W)
{
    printf("[ ");
    for (int i=0; i<t; ++i) {
        printf("%d ", c[i]);
    }
    printf("] = %d\n", W);
}

int main()
{   
    for (int j=1; j<=n-1; ++j) {
        delta[j] = w[j] - w[j-1];
    }
    
    int t=0;
    c[0] = n;
    int r = N;

f2: 
    visit(t, c+1, N-r);
    
    if (c[t] > 0 && r >= w[0]) {
        t = t + 1;
        c[t] = 0;
        r = r - w[0];
        goto f2;
    }
    
f4: 
    if (t == 0) {
        return 0;
    }
    
    if (c[t-1] > c[t] + 1 && r >= delta[c[t]+1]) {
        c[t] = c[t] + 1;
        r = r - delta[c[t]];
        goto f2;
    }
    
    r = r + w[c[t]];
    t = t - 1;
    goto f4;
}
 

[B@R5uk]

B@R5uk в сообщении #1287281 писал(а):

Осталось понять, как пропускать группы неудачных комбинаций.

Это, оказывается, ни чуть не сложнее (а то и проще), чем просто переход к следующей комбинации. Для пропуска группы необходимо не просто добавить следующий элемент в подмножество, а вместе с добавлением удалить элемент, добавленный на прошлом шаге. Разумеется, необходимо скопипастить соответствующий индекс элемента добавленного ещё на шаг ранее. Остальное — работа алгоритма. Так же, использовать конечный автомат на четыре состояния — это откровенный перебор, и по многим причинам. Во-первых проблему с удалением и одновременным добавлением самого первого элемента можно решить значительно проще (смотри закомментированный "IF" в коде), а во-вторых, овчинка выделки не стоит, поскольку большую часть времени алгоритм проведёт перебирая элементы далёкие от самого первого (за счёт пропусков неудачных состояний), так что дополнительная проверка лишь увеличит время выполнения, хотя вроде бы призвана уменьшить его.

Код получился такой (пропуск в качестве демонстрации выполняется только для одной единственной позиции):

Используется синтаксис Java

public class StudySubsetSearch8 {
        
        private static final int size = 5;
        private static final int skippingPosition = 17;
        private static int position = 0;
        
        public static void main(String[] args) {
                int[] array = new int[size];
                int[] indices = new int[size];
                int index, lastIndex;
                boolean isSkipping = false;
                index = size;
                while (true) {
                        display(array);
                        if (0 == index) {
                                index = indices[0];
                                if (size == index) {
                                        break;
                                }
                                lastIndex = indices[index];
                                array[index] = 0;
                                --index;
                                indices[index] = lastIndex;
//                              if (0 != index) {
                                array[0] = 0;
                                array[index] = 1;
//                              }
                        } else {
                                if (isSkipping) {
                                        lastIndex = indices[index];
                                        array[index] = 0;
                                } else {
                                        lastIndex = index;
                                }
                                --index;
                                indices[index] = lastIndex;
                                array[index] = 1;
                        }
                        isSkipping = isSkippingPosition();
                }
        }
        
        private static void display(int[] array) {
                int n, size;
                size = array.length;
                for (n = 0; size > n; ++n) {
                        System.out.print(array[n]);
                }
                System.out.println();
        }
        
        private static boolean isSkippingPosition() {
                ++position;
                return skippingPosition == position;
        }
}
 

mustitz в сообщении #1287295 писал(а):

void visit(...)
{
printf("[ ");
for (int i=0; i<t; ++i) {
printf("%d ", c[i]);
}
printf("] = %d\n", W);
}

Так вот что означает "посетить сочетание"!!! А я то думал!

Вообще, в ваш код ещё не вникал (особо напрягает код с именами переменных в одну букву — нечеловеческое название, не разберёшь зачем она нужна), но наличие "GOTO" живо бросается в глаза. Впрочем, я понимаю, что это в прямом смысле слова дословная реализация.

[B@R5uk]

arseniiv в сообщении #1286956 писал(а):

Кластеризовать элементы в какое-то дерево по их суммам, чтобы побольше отбрасывать перелётов, или по дополнениям сумм до полной, чтобы отбрасывать недолёты (а вот как совместить то и это, не представляю).

Погонял свой алгоритм:

Используется синтаксис Java

import java.util.*;

public class StudySubsetSearch9 {
        
        private static final Random rng = new Random();
        private static final int maxRand = 20;
        private static final int size = 10;
        private static final int[] values = new int[size];
        
        public static void main(String[] args) {
                int n, value, totalSum, sum, index, lastIndex, count;
                int[] array, indices;
                boolean isSkipping;
                totalSum = 0;
                for (n = 0; n < size; n++) {
                        value = 1 + rng.nextInt(maxRand);
                        values[n] = value;
                        totalSum += value;
                }
                Arrays.sort(values);
                value = totalSum / 3 + rng.nextInt(maxRand);
                array = new int[size];
                indices = new int[size];
                isSkipping = false;
                index = size;
                sum = 0;
                count = 0;
                display(values);
                while (true) {
                        display(array, values, sum, value, false);
                        if (0 == index) {
                                index = indices[0];
                                if (size == index) {
                                        break;
                                }
                                lastIndex = indices[index];
                                array[index] = 0;
                                sum -= values[index];
                                --index;
                                indices[index] = lastIndex;
                                array[0] = 0;
                                sum -= values[0];
                                array[index] = 1;
                                sum += values[index];
                        } else {
                                if (isSkipping) {
                                        lastIndex = indices[index];
                                        array[index] = 0;
                                        sum -= values[index];
                                } else {
                                        lastIndex = index;
                                }
                                --index;
                                indices[index] = lastIndex;
                                array[index] = 1;
                                sum += values[index];
                        }
                        if (sum > value) {
                                isSkipping = true;
                        } else if (sum == value) {
                                isSkipping = true;
                                ++count;
                        } else {
                                isSkipping = false;
                        }
                }
                System.out.println();
                System.out.print("Match count: ");
                System.out.println(count);
        }
        
        private static void display(int[] array, int[] values, int sum, int value, boolean isFlagged) {
                int n, size;
                size = array.length;
                System.out.print(array[0]);
                if (isFlagged) {
                        System.out.print("*");
                        System.out.print(values[0]);
                }
                for (n = 1; size > n; ++n) {
                        if (isFlagged) {
                                System.out.print(" + ");
                        }
                        System.out.print(array[n]);
                        if (isFlagged) {
                                System.out.print("*");
                                System.out.print(values[n]);
                        }
                }
                System.out.print(" = ");
                System.out.print(sum);
                System.out.print(" (");
                System.out.print(value);
                System.out.println(")");
        }
        
        private static void display(int[] values) {
                int n, size;
                size = values.length;
                System.out.print(values[0]);
                for (n = 1; size > n; ++n) {
                        System.out.print(", ");
                        System.out.print(values[n]);
                }
                System.out.println();
        }
}

Результаты получаются приблизительно такие (предварительная сортировка множества исходных значений весьма важна — она позволяет сходу выкинуть множество комбинаций с "перебором", особенно учитывая, что искомая сумма почти в трое меньше полной суммы всех элементов):

(Оффтоп)

3, 4, 7, 10, 10, 10, 13, 16, 17, 19
0000000000 = 0 (45)
0000000001 = 19 (45)
0000000011 = 36 (45)
0000000111 = 52 (45)
0000001011 = 49 (45)
0000010011 = 46 (45)
0000100011 = 46 (45)
0001000011 = 46 (45)
0010000011 = 43 (45)
0110000011 = 47 (45)
1010000011 = 46 (45)
0100000011 = 40 (45)
1100000011 = 43 (45)
1000000011 = 39 (45)
0000000101 = 35 (45)
0000001101 = 48 (45)
0000010101 = 45 (45)
0000100101 = 45 (45)
0001000101 = 45 (45)
0010000101 = 42 (45)
0110000101 = 46 (45)
1010000101 = 45 (45)
0100000101 = 39 (45)
1100000101 = 42 (45)
1000000101 = 38 (45)
0000001001 = 32 (45)
0000011001 = 42 (45)
0000111001 = 52 (45)
0001011001 = 52 (45)
0010011001 = 49 (45)
0100011001 = 46 (45)
1000011001 = 45 (45)
0000101001 = 42 (45)
0001101001 = 52 (45)
0010101001 = 49 (45)
0100101001 = 46 (45)
1000101001 = 45 (45)
0001001001 = 42 (45)
0011001001 = 49 (45)
0101001001 = 46 (45)
1001001001 = 45 (45)
0010001001 = 39 (45)
0110001001 = 43 (45)
1110001001 = 46 (45)
1010001001 = 42 (45)
0100001001 = 36 (45)
1100001001 = 39 (45)
1000001001 = 35 (45)
0000010001 = 29 (45)
0000110001 = 39 (45)
0001110001 = 49 (45)
0010110001 = 46 (45)
0100110001 = 43 (45)
1100110001 = 46 (45)
1000110001 = 42 (45)
0001010001 = 39 (45)
0011010001 = 46 (45)
0101010001 = 43 (45)
1101010001 = 46 (45)
1001010001 = 42 (45)
0010010001 = 36 (45)
0110010001 = 40 (45)
1110010001 = 43 (45)
1010010001 = 39 (45)
0100010001 = 33 (45)
1100010001 = 36 (45)
1000010001 = 32 (45)
0000100001 = 29 (45)
0001100001 = 39 (45)
0011100001 = 46 (45)
0101100001 = 43 (45)
1101100001 = 46 (45)
1001100001 = 42 (45)
0010100001 = 36 (45)
0110100001 = 40 (45)
1110100001 = 43 (45)
1010100001 = 39 (45)
0100100001 = 33 (45)
1100100001 = 36 (45)
1000100001 = 32 (45)
0001000001 = 29 (45)
0011000001 = 36 (45)
0111000001 = 40 (45)
1111000001 = 43 (45)
1011000001 = 39 (45)
0101000001 = 33 (45)
1101000001 = 36 (45)
1001000001 = 32 (45)
0010000001 = 26 (45)
0110000001 = 30 (45)
1110000001 = 33 (45)
1010000001 = 29 (45)
0100000001 = 23 (45)
1100000001 = 26 (45)
1000000001 = 22 (45)
0000000010 = 17 (45)
0000000110 = 33 (45)
0000001110 = 46 (45)
0000010110 = 43 (45)
0000110110 = 53 (45)
0001010110 = 53 (45)
0010010110 = 50 (45)
0100010110 = 47 (45)
1000010110 = 46 (45)
0000100110 = 43 (45)
0001100110 = 53 (45)
0010100110 = 50 (45)
0100100110 = 47 (45)
1000100110 = 46 (45)
0001000110 = 43 (45)
0011000110 = 50 (45)
0101000110 = 47 (45)
1001000110 = 46 (45)
0010000110 = 40 (45)
0110000110 = 44 (45)
1110000110 = 47 (45)
1010000110 = 43 (45)
0100000110 = 37 (45)
1100000110 = 40 (45)
1000000110 = 36 (45)
0000001010 = 30 (45)
0000011010 = 40 (45)
0000111010 = 50 (45)
0001011010 = 50 (45)
0010011010 = 47 (45)
0100011010 = 44 (45)
1100011010 = 47 (45)
1000011010 = 43 (45)
0000101010 = 40 (45)
0001101010 = 50 (45)
0010101010 = 47 (45)
0100101010 = 44 (45)
1100101010 = 47 (45)
1000101010 = 43 (45)
0001001010 = 40 (45)
0011001010 = 47 (45)
0101001010 = 44 (45)
1101001010 = 47 (45)
1001001010 = 43 (45)
0010001010 = 37 (45)
0110001010 = 41 (45)
1110001010 = 44 (45)
1010001010 = 40 (45)
0100001010 = 34 (45)
1100001010 = 37 (45)
1000001010 = 33 (45)
0000010010 = 27 (45)
0000110010 = 37 (45)
0001110010 = 47 (45)
0010110010 = 44 (45)
0110110010 = 48 (45)
1010110010 = 47 (45)
0100110010 = 41 (45)
1100110010 = 44 (45)
1000110010 = 40 (45)
0001010010 = 37 (45)
0011010010 = 44 (45)
0111010010 = 48 (45)
1011010010 = 47 (45)
0101010010 = 41 (45)
1101010010 = 44 (45)
1001010010 = 40 (45)
0010010010 = 34 (45)
0110010010 = 38 (45)
1110010010 = 41 (45)
1010010010 = 37 (45)
0100010010 = 31 (45)
1100010010 = 34 (45)
1000010010 = 30 (45)
0000100010 = 27 (45)
0001100010 = 37 (45)
0011100010 = 44 (45)
0111100010 = 48 (45)
1011100010 = 47 (45)
0101100010 = 41 (45)
1101100010 = 44 (45)
1001100010 = 40 (45)
0010100010 = 34 (45)
0110100010 = 38 (45)
1110100010 = 41 (45)
1010100010 = 37 (45)
0100100010 = 31 (45)
1100100010 = 34 (45)
1000100010 = 30 (45)
0001000010 = 27 (45)
0011000010 = 34 (45)
0111000010 = 38 (45)
1111000010 = 41 (45)
1011000010 = 37 (45)
0101000010 = 31 (45)
1101000010 = 34 (45)
1001000010 = 30 (45)
0010000010 = 24 (45)
0110000010 = 28 (45)
1110000010 = 31 (45)
1010000010 = 27 (45)
0100000010 = 21 (45)
1100000010 = 24 (45)
1000000010 = 20 (45)
0000000100 = 16 (45)
0000001100 = 29 (45)
0000011100 = 39 (45)
0000111100 = 49 (45)
0001011100 = 49 (45)
0010011100 = 46 (45)
0100011100 = 43 (45)
1100011100 = 46 (45)
1000011100 = 42 (45)
0000101100 = 39 (45)
0001101100 = 49 (45)
0010101100 = 46 (45)
0100101100 = 43 (45)
1100101100 = 46 (45)
1000101100 = 42 (45)
0001001100 = 39 (45)
0011001100 = 46 (45)
0101001100 = 43 (45)
1101001100 = 46 (45)
1001001100 = 42 (45)
0010001100 = 36 (45)
0110001100 = 40 (45)
1110001100 = 43 (45)
1010001100 = 39 (45)
0100001100 = 33 (45)
1100001100 = 36 (45)
1000001100 = 32 (45)
0000010100 = 26 (45)
0000110100 = 36 (45)
0001110100 = 46 (45)
0010110100 = 43 (45)
0110110100 = 47 (45)
1010110100 = 46 (45)
0100110100 = 40 (45)
1100110100 = 43 (45)
1000110100 = 39 (45)
0001010100 = 36 (45)
0011010100 = 43 (45)
0111010100 = 47 (45)
1011010100 = 46 (45)
0101010100 = 40 (45)
1101010100 = 43 (45)
1001010100 = 39 (45)
0010010100 = 33 (45)
0110010100 = 37 (45)
1110010100 = 40 (45)
1010010100 = 36 (45)
0100010100 = 30 (45)
1100010100 = 33 (45)
1000010100 = 29 (45)
0000100100 = 26 (45)
0001100100 = 36 (45)
0011100100 = 43 (45)
0111100100 = 47 (45)
1011100100 = 46 (45)
0101100100 = 40 (45)
1101100100 = 43 (45)
1001100100 = 39 (45)
0010100100 = 33 (45)
0110100100 = 37 (45)
1110100100 = 40 (45)
1010100100 = 36 (45)
0100100100 = 30 (45)
1100100100 = 33 (45)
1000100100 = 29 (45)
0001000100 = 26 (45)
0011000100 = 33 (45)
0111000100 = 37 (45)
1111000100 = 40 (45)
1011000100 = 36 (45)
0101000100 = 30 (45)
1101000100 = 33 (45)
1001000100 = 29 (45)
0010000100 = 23 (45)
0110000100 = 27 (45)
1110000100 = 30 (45)
1010000100 = 26 (45)
0100000100 = 20 (45)
1100000100 = 23 (45)
1000000100 = 19 (45)
0000001000 = 13 (45)
0000011000 = 23 (45)
0000111000 = 33 (45)
0001111000 = 43 (45)
0011111000 = 50 (45)
0101111000 = 47 (45)
1001111000 = 46 (45)
0010111000 = 40 (45)
0110111000 = 44 (45)
1110111000 = 47 (45)
1010111000 = 43 (45)
0100111000 = 37 (45)
1100111000 = 40 (45)
1000111000 = 36 (45)
0001011000 = 33 (45)
0011011000 = 40 (45)
0111011000 = 44 (45)
1111011000 = 47 (45)
1011011000 = 43 (45)
0101011000 = 37 (45)
1101011000 = 40 (45)
1001011000 = 36 (45)
0010011000 = 30 (45)
0110011000 = 34 (45)
1110011000 = 37 (45)
1010011000 = 33 (45)
0100011000 = 27 (45)
1100011000 = 30 (45)
1000011000 = 26 (45)
0000101000 = 23 (45)
0001101000 = 33 (45)
0011101000 = 40 (45)
0111101000 = 44 (45)
1111101000 = 47 (45)
1011101000 = 43 (45)
0101101000 = 37 (45)
1101101000 = 40 (45)
1001101000 = 36 (45)
0010101000 = 30 (45)
0110101000 = 34 (45)
1110101000 = 37 (45)
1010101000 = 33 (45)
0100101000 = 27 (45)
1100101000 = 30 (45)
1000101000 = 26 (45)
0001001000 = 23 (45)
0011001000 = 30 (45)
0111001000 = 34 (45)
1111001000 = 37 (45)
1011001000 = 33 (45)
0101001000 = 27 (45)
1101001000 = 30 (45)
1001001000 = 26 (45)
0010001000 = 20 (45)
0110001000 = 24 (45)
1110001000 = 27 (45)
1010001000 = 23 (45)
0100001000 = 17 (45)
1100001000 = 20 (45)
1000001000 = 16 (45)
0000010000 = 10 (45)
0000110000 = 20 (45)
0001110000 = 30 (45)
0011110000 = 37 (45)
0111110000 = 41 (45)
1111110000 = 44 (45)
1011110000 = 40 (45)
0101110000 = 34 (45)
1101110000 = 37 (45)
1001110000 = 33 (45)
0010110000 = 27 (45)
0110110000 = 31 (45)
1110110000 = 34 (45)
1010110000 = 30 (45)
0100110000 = 24 (45)
1100110000 = 27 (45)
1000110000 = 23 (45)
0001010000 = 20 (45)
0011010000 = 27 (45)
0111010000 = 31 (45)
1111010000 = 34 (45)
1011010000 = 30 (45)
0101010000 = 24 (45)
1101010000 = 27 (45)
1001010000 = 23 (45)
0010010000 = 17 (45)
0110010000 = 21 (45)
1110010000 = 24 (45)
1010010000 = 20 (45)
0100010000 = 14 (45)
1100010000 = 17 (45)
1000010000 = 13 (45)
0000100000 = 10 (45)
0001100000 = 20 (45)
0011100000 = 27 (45)
0111100000 = 31 (45)
1111100000 = 34 (45)
1011100000 = 30 (45)
0101100000 = 24 (45)
1101100000 = 27 (45)
1001100000 = 23 (45)
0010100000 = 17 (45)
0110100000 = 21 (45)
1110100000 = 24 (45)
1010100000 = 20 (45)
0100100000 = 14 (45)
1100100000 = 17 (45)
1000100000 = 13 (45)
0001000000 = 10 (45)
0011000000 = 17 (45)
0111000000 = 21 (45)
1111000000 = 24 (45)
1011000000 = 20 (45)
0101000000 = 14 (45)
1101000000 = 17 (45)
1001000000 = 13 (45)
0010000000 = 7 (45)
0110000000 = 11 (45)
1110000000 = 14 (45)
1010000000 = 10 (45)
0100000000 = 4 (45)
1100000000 = 7 (45)
1000000000 = 3 (45)

Match count: 7

Наблюдая эти результаты становится ясно, что вопрос оптимизации как по перелёту, так и по недолёту стоит очень остро. Большую часть времени в поисках конкретной суммы сейчас алгоритм тратит перебирая те комбинации, которые заведомо не подойдут именно из-за недостаточности полной суммы всех оставшихся перебираемых слагаемых. Причём это касается и середины алгоритма: там тоже можно выделить области комбинаций, в которых одна часть элементов фиксирована, а другая — перебираемая — в сумме не дополняет первую до нужной кондиции.

Тут ещё есть более тонкий вопрос, касающийся повторяющихся элементов, но его лучше оставить на потом.

[arseniiv]

B@R5uk в сообщении #1287477 писал(а):

Большую часть времени в поисках конкретной суммы сейчас алгоритм тратит перебирая те комбинации, которые заведомо не подойдут именно из-за недостаточности полной суммы всех оставшихся перебираемых слагаемых.

Если посчитать сумму всех элементов и вычитать те, отсутствие которых мы зафиксировали, то когда она становится меньше, все соответствующие подмножества перебирать не будем. В терминах дерева это отсечение на 0-рёбрах, аналогично тому, как отсекаются 1-рёбра, сами слишком большие для вхождения в ожидаемый кусок суммы. Насколько много будет отсекать такое дополнение?

Кстати, не обязательно было приводить суммы вообще всех подмножеств, было бы лучше как-то сократить статистику, указав, например, сколько с недолётом, сколько с перелётом и сколько как раз.

B@R5uk в сообщении #1287477 писал(а):

Тут ещё есть более тонкий вопрос, касающийся повторяющихся элементов, но его лучше оставить на потом.

Да, это стоит оптимизировать. Можно не хранить их по отдельным индексам, а вместо этого сделать перечисление подмультимножеств заданного, допуская кроме нулей и единиц и другие числа, не большие числа вхождений заданного элемента. И алгоритм перечисления, и обход (эфемерного) дерева должны обобщаться (перечисление я, кажется, писал когда-то).

UPD: Ой какой бред написал. Перечислить все подмультимножества проще простого, я писал перечисление сочетаний.

[B@R5uk]

arseniiv в сообщении #1287492 писал(а):

Кстати, не обязательно было приводить суммы вообще всех подмножеств, было бы лучше как-то сократить статистику, указав, например, сколько с недолётом, сколько с перелётом и сколько как раз.

Ну, там не все подмножества, только 400 с хвостиком... из 1024. Хотя идея подсчёта статистики весьма хороша!

arseniiv в сообщении #1287492 писал(а):

Если посчитать сумму всех элементов и вычитать те, отсутствие которых мы зафиксировали, то когда она становится меньше, все соответствующие подмножества перебирать не будем.

Вопрос в том, как это реализовать. Например, в результате выше, после строк
0010010001 = 36 (45)
0110010001 = 40 (45)
1110010001 = 43 (45)
можно не перебирать строки
1010010001 = 39 (45)
0100010001 = 33 (45)
1100010001 = 36 (45)
1000010001 = 32 (45)
а сразу перейти к строкам
0000100001 = 29 (45)
0001100001 = 39 (45)
0011100001 = 46 (45)

[B@R5uk]

Я придумал простой и действенный способ пропуска недолётов. Вот наглядный пример. Когда перебор от комбинации
1001010001 = 42 (45) переходит к комбинации
0010010001 = 36 (45) то это является началом перебора подмножества комбинаций вида
xxx0010001 = ?? (45). Если сумма всех элементов, помеченных иксами, в сумме с остальными выбранными элементами не дотягивает до искомой суммы, то такое подмножество комбинаций перебирать нет смысла. Можно сразу переходить к комбинации
0000100001 = 29 (45), которая является первой комбинацией нового подмножества вида
xxxxx00001 = ?? (45). Однако, это новое подмножество тоже надо подвергнуть проверке на отсечение по недолёту. Чтобы не делать это во вложенном цикле, а сделать на новой итерации основного цикла, необходимо после проверки подмножества комбинаций вида
xxx0010001 = ?? (45) переходить не к первой комбинации нового подмножества, а к последней комбинации проверенного подмножества, то есть к комбинации
1000010001 = 32 (45), после которой по списку сразу идёт
0000100001 = 29 (45), проверкой которой займётся следующая итерация.

Сухой остаток. На входе имеется
1001010001 = 42 (45). Проверяем
xxx0010001 = ?? (45), используя для предварительно посчитанный массив кумулятивных сумм первых элементов исходного множества. Если недолёт, то переходим к
1000010001 = 32 (45). Если перелёт, то необходим полный перебор, поэтому переходим к
0010010001 = 36 (45). Если же попадание, то это можно сразу зафиксировать, а затем, как и в случае недолёта, перейти к
1000010001 = 32 (45).

В таком виде алгоритм сохранит свою целостность: никаких вложенных циклов и на каждом этапе над промежуточной суммой производится не более трёх операций сложения/вычитания.

Здесь есть, правда, одна тонкость. Комбинация
1100010001 = 36 (45) обрабатывается той же частью кода, что и комбинации, описанные выше. Однако, вне зависимости от результата проверки на отсечение, переход будет осуществляться к комбинации
1000010001 = 32 (45). Поэтому в таких случаях проверку делать не надо.

В то же время с комбинацией
1010010001 = 39 (45) всё значительно лучше: удачная проверка позволяет пропустить две итерации алгоритма. Думаю, в этом случае овчинка выделки уже стоит.

И да, при перемещении единичек надо не забывать копировать индексы!

[B@R5uk]

В конце-концов вот такой код у меня получился:

Используется синтаксис Java

import java.util.*;

public class StudySubsetSearch10 {
        
        private static final Random rng = new Random();
        private static final int maxRand = 20;
        private static final int size = 10;
        private static final int[] values = new int[size];
        private static final int[] cumulativeSums = new int[size];
        
        public static void main(String[] args) {
                int n, value, totalSum, sum, index, lastIndex;
                int matchCount, undershotsCount, overshotsCount;
                int subsetsCount, undershotSkips, overshotSkips;
                int[] array, indices;
                boolean isSkipping;
                for (n = 0; n < size; n++) {
                        values[n] = 1 + rng.nextInt(maxRand);
                }
                Arrays.sort(values);
                totalSum = 0;
                for (n = 1; n < size; n++) {
                        totalSum += values[n];
                        cumulativeSums[n] = totalSum;
                }
                totalSum += values[0];
                value = totalSum / 3 + rng.nextInt(maxRand);
                array = new int[size];
                indices = new int[size];
                isSkipping = false;
                index = size;
                sum = 0;
                matchCount = 0;
                subsetsCount = 0;
                undershotsCount = 0;
                overshotsCount = 0;
                undershotSkips = 0;
                overshotSkips = 0;
                display(values);
                display(cumulativeSums);
                while (true) {
                        display(array, sum, value);
                        ++subsetsCount;
                        if (value < sum) {
                                isSkipping = true;
                        } else if (value == sum) {
                                isSkipping = true;
                                ++matchCount;
                        } else {
                                isSkipping = false;
                        }
                        if (0 == index) {
                                index = indices[0];
                                if (size == index) {
                                        break;
                                }
                                lastIndex = indices[index];
                                array[index] = 0;
                                sum -= values[index];
                                --index;
                                if (0 < index) {
                                        totalSum = cumulativeSums[index] + sum;
                                        if (value >= totalSum) {
                                                if (value == totalSum) {
                                                        ++matchCount;
                                                }
                                                indices[0] = lastIndex;
                                                ++undershotsCount;
                                                undershotSkips += (1 << index + 1) - 2;
                                                index = 0;
                                                continue;
                                        }
                                }
                                indices[index] = lastIndex;
                                array[0] = 0;
                                sum -= values[0];
                                array[index] = 1;
                                sum += values[index];
                                continue;
                        }
                        if (isSkipping) {
                                lastIndex = indices[index];
                                array[index] = 0;
                                sum -= values[index];
                                ++overshotsCount;
                                overshotSkips += (1 << index) - 1;
                        } else {
                                lastIndex = index;
                        }
                        --index;
                        indices[index] = lastIndex;
                        array[index] = 1;
                        sum += values[index];
                }
                System.out.println();
                System.out.print("Match count: ");
                System.out.println(matchCount);
                System.out.print("Subsets searched: ");
                System.out.println(subsetsCount);
                System.out.print("Overshots count: ");
                System.out.println(overshotsCount);
                System.out.print("Overshot skips: ");
                System.out.println(overshotSkips);
                System.out.print("Undershots count: ");
                System.out.println(undershotsCount);
                System.out.print("Undershot skips: ");
                System.out.println(undershotSkips);
                System.out.print("Total skips: ");
                System.out.println(undershotSkips + overshotSkips);
                System.out.print("Total subsets count: ");
                System.out.println(1 << size);
        }
        
        private static void display(int[] array, int sum, int value) {
                int n, size;
                size = array.length;
                System.out.print(array[0]);
                for (n = 1; size > n; ++n) {
                        System.out.print(array[n]);
                }
                System.out.print(" -> ");
                System.out.print(sum);
                System.out.print(" (");
                System.out.print(value);
                if (value == sum) {
                        System.out.println(") Match!");
                } else {
                        System.out.println(")");
                }
        }
        
        private static void display(int[] values) {
                int n, size;
                size = values.length;
                System.out.print(values[0]);
                for (n = 1; size > n; ++n) {
                        System.out.print(", ");
                        System.out.print(values[n]);
                }
                System.out.println();
        }
}

И этот код выдаёт приблизительно вот такие результаты:

(Оффтоп)

1, 2, 2, 3, 5, 7, 10, 14, 18, 20
0, 2, 4, 7, 12, 19, 29, 43, 61, 81
0000000000 -> 0 (43)
0000000001 -> 20 (43)
0000000011 -> 38 (43)
0000000111 -> 52 (43)
0000001011 -> 48 (43)
0000010011 -> 45 (43)
0000100011 -> 43 (43) Match!
0001000011 -> 41 (43)
0011000011 -> 43 (43) Match!
0101000011 -> 43 (43) Match!
1001000011 -> 42 (43)
1000000011 -> 39 (43)
0000000101 -> 34 (43)
0000001101 -> 44 (43)
0000010101 -> 41 (43)
0000110101 -> 46 (43)
0001010101 -> 44 (43)
0010010101 -> 43 (43) Match!
0100010101 -> 43 (43) Match!
1000010101 -> 42 (43)
0000100101 -> 39 (43)
0001100101 -> 42 (43)
0011100101 -> 44 (43)
0101100101 -> 44 (43)
1001100101 -> 43 (43) Match!
0010100101 -> 41 (43)
0110100101 -> 43 (43) Match!
1010100101 -> 42 (43)
1000100101 -> 40 (43)
1000000101 -> 35 (43)
0000001001 -> 30 (43)
0000011001 -> 37 (43)
0000111001 -> 42 (43)
0001111001 -> 45 (43)
0010111001 -> 44 (43)
0100111001 -> 44 (43)
1000111001 -> 43 (43) Match!
0001011001 -> 40 (43)
0011011001 -> 42 (43)
0111011001 -> 44 (43)
1011011001 -> 43 (43) Match!
1001011001 -> 41 (43)
1000011001 -> 38 (43)
1000001001 -> 31 (43)
1000000001 -> 21 (43)
0000000010 -> 18 (43)
0000000110 -> 32 (43)
0000001110 -> 42 (43)
0000011110 -> 49 (43)
0000101110 -> 47 (43)
0001001110 -> 45 (43)
0010001110 -> 44 (43)
0100001110 -> 44 (43)
1000001110 -> 43 (43) Match!
0000010110 -> 39 (43)
0000110110 -> 44 (43)
0001010110 -> 42 (43)
0011010110 -> 44 (43)
0101010110 -> 44 (43)
1001010110 -> 43 (43) Match!
0010010110 -> 41 (43)
0110010110 -> 43 (43) Match!
1010010110 -> 42 (43)
1000010110 -> 40 (43)
0000100110 -> 37 (43)
0001100110 -> 40 (43)
0011100110 -> 42 (43)
0111100110 -> 44 (43)
1011100110 -> 43 (43) Match!
1001100110 -> 41 (43)
1000100110 -> 38 (43)
1000000110 -> 33 (43)
0000001010 -> 28 (43)
0000011010 -> 35 (43)
0000111010 -> 40 (43)
0001111010 -> 43 (43) Match!
0010111010 -> 42 (43)
0110111010 -> 44 (43)
1010111010 -> 43 (43) Match!
1000111010 -> 41 (43)
1000011010 -> 36 (43)
1000001010 -> 29 (43)
1000000010 -> 19 (43)
0000000100 -> 14 (43)
0000001100 -> 24 (43)
0000011100 -> 31 (43)
0000111100 -> 36 (43)
0001111100 -> 39 (43)
0011111100 -> 41 (43)
0111111100 -> 43 (43) Match!
1011111100 -> 42 (43)
1001111100 -> 40 (43)
1000111100 -> 37 (43)
1000011100 -> 32 (43)
1000001100 -> 25 (43)
1000000100 -> 15 (43)
1000000000 -> 1 (43)

Match count: 22
Subsets searched: 97
Overshots count: 31
Overshot skips: 433
Undershots count: 21
Undershot skips: 494
Total skips: 927
Total subsets count: 1024

Надо заметить, что кумулятивная сумма для отбрасывания недолётов считается без первого элемента. Это нужно, чтобы не делать лишних вычислений в теле цикла. Вообще, смотрю я на эти результаты и вижу забавные лесенки и треугольнички. Когда я придумывал последовательность перебора подмножеств я и не думал, что всё так хорошо получится: ни про то, что каждая итерация будет требовать не больше трёх арифметических операций над суммой, ни, тем более, что с её же помощью можно будет отсеивать недолёты. Заботился исключительно о перелётах. Хотя, конечно, алгоритм ещё не факт, что полностью лишён всяких ошибок. Как это обычно водится, в редких случаях может вылезать какая-нибудь редкая и поэтому очень неприятная бяка. В качестве крэш-теста этого алгоритма теперь надо попробовать решить самую сложную задачу программирования.

[arseniiv]

(От меня вам устаревший пост, который был начат давно.) Фактически, счётчик подмножеств должен уметь отзываться на три «статуса перебора» — много/ровно (можно исключить ситуации «много» заранее, не разрешая выбирать слишком много какого-нибудь элемента), мало и неизвестно. Только при последнем делается самый маленький шаг, при остальных пропуски.

Вот какой протокол у моей наконец-то допиленной программы на ваших данных из спойлера (слагаемые также идут от больших к меньшим, но не повторяются):

Используется синтаксис Text

{ *, *, *, *, *, *, *, * }      ?
{ 1, *, *, *, *, *, *, * }      ?
{ 1, 1, *, *, *, *, *, * }      ?
{ 1, 1, 0, *, *, *, *, * }      ?
{ 1, 1, 0, 0, *, *, *, * }      ?
{ 1, 1, 0, 0, 0, *, *, * }      ?
{ 1, 1, 0, 0, 0, 1, *, * }      ?
{ 1, 1, 0, 0, 0, 1, 0, * }      ?
{ 1, 1, 0, 0, 0, 1, 0, 0 }      <
{ 1, 1, 0, 0, 0, 0, *, * }      <
{ 1, 0, *, *, *, *, *, * }      ?
{ 1, 0, 1, *, *, *, *, * }      ?
{ 1, 0, 1, 0, *, *, *, * }      ?
{ 1, 0, 1, 0, 1, *, *, * }      =
{ 1, 0, 1, 0, 0, *, *, * }      ?
{ 1, 0, 1, 0, 0, 1, *, * }      ?
{ 1, 0, 1, 0, 0, 1, 0, * }      ?
{ 1, 0, 1, 0, 0, 1, 0, 1 }      =
{ 1, 0, 1, 0, 0, 1, 0, 0 }      <
{ 1, 0, 1, 0, 0, 0, *, * }      <
{ 1, 0, 0, *, *, *, *, * }      ?
{ 1, 0, 0, 1, *, *, *, * }      ?
{ 1, 0, 0, 1, 1, *, *, * }      ?
{ 1, 0, 0, 1, 1, 0, *, * }      ?
{ 1, 0, 0, 1, 1, 0, 0, * }      ?
{ 1, 0, 0, 1, 1, 0, 0, 1 }      =
{ 1, 0, 0, 1, 1, 0, 0, 0 }      <
{ 1, 0, 0, 1, 0, *, *, * }      ?
{ 1, 0, 0, 1, 0, 1, *, * }      ?
{ 1, 0, 0, 1, 0, 1, 1, * }      ?
{ 1, 0, 0, 1, 0, 1, 1, 0 }      <
{ 1, 0, 0, 1, 0, 1, 0, * }      <
{ 1, 0, 0, 1, 0, 0, *, * }      <
{ 1, 0, 0, 0, *, *, *, * }      ?
{ 1, 0, 0, 0, 2, *, *, * }      ?
{ 1, 0, 0, 0, 2, 0, *, * }      ?
{ 1, 0, 0, 0, 2, 0, 1, * }      ?
{ 1, 0, 0, 0, 2, 0, 1, 0 }      <
{ 1, 0, 0, 0, 2, 0, 0, * }      <
{ 1, 0, 0, 0, 1, *, *, * }      <
{ 0, *, *, *, *, *, *, * }      ?
{ 0, 1, *, *, *, *, *, * }      ?
{ 0, 1, 1, *, *, *, *, * }      ?
{ 0, 1, 1, 0, *, *, *, * }      ?
{ 0, 1, 1, 0, 1, *, *, * }      ?
{ 0, 1, 1, 0, 1, 0, *, * }      ?
{ 0, 1, 1, 0, 1, 0, 0, * }      ?
{ 0, 1, 1, 0, 1, 0, 0, 0 }      <
{ 0, 1, 1, 0, 0, *, *, * }      ?
{ 0, 1, 1, 0, 0, 1, *, * }      ?
{ 0, 1, 1, 0, 0, 1, 1, * }      ?
{ 0, 1, 1, 0, 0, 1, 1, 0 }      <
{ 0, 1, 1, 0, 0, 1, 0, * }      <
{ 0, 1, 1, 0, 0, 0, *, * }      <
{ 0, 1, 0, *, *, *, *, * }      ?
{ 0, 1, 0, 1, *, *, *, * }      ?
{ 0, 1, 0, 1, 1, *, *, * }      ?
{ 0, 1, 0, 1, 1, 0, *, * }      ?
{ 0, 1, 0, 1, 1, 0, 1, * }      ?
{ 0, 1, 0, 1, 1, 0, 1, 0 }      <
{ 0, 1, 0, 1, 1, 0, 0, * }      <
{ 0, 1, 0, 1, 0, *, *, * }      <
{ 0, 1, 0, 0, *, *, *, * }      ?
{ 0, 1, 0, 0, 2, *, *, * }      ?
{ 0, 1, 0, 0, 2, 1, *, * }      ?
{ 0, 1, 0, 0, 2, 1, 0, * }      ?
{ 0, 1, 0, 0, 2, 1, 0, 0 }      <
{ 0, 1, 0, 0, 2, 0, *, * }      <
{ 0, 1, 0, 0, 1, *, *, * }      <
{ 0, 0, *, *, *, *, *, * }      ?
{ 0, 0, 1, *, *, *, *, * }      ?
{ 0, 0, 1, 1, *, *, *, * }      ?
{ 0, 0, 1, 1, 1, *, *, * }      ?
{ 0, 0, 1, 1, 1, 0, *, * }      ?
{ 0, 0, 1, 1, 1, 0, 1, * }      ?
{ 0, 0, 1, 1, 1, 0, 1, 0 }      <
{ 0, 0, 1, 1, 1, 0, 0, * }      <
{ 0, 0, 1, 1, 0, *, *, * }      <
{ 0, 0, 1, 0, *, *, *, * }      ?
{ 0, 0, 1, 0, 2, *, *, * }      ?
{ 0, 0, 1, 0, 2, 1, *, * }      ?
{ 0, 0, 1, 0, 2, 1, 0, * }      ?
{ 0, 0, 1, 0, 2, 1, 0, 0 }      <
{ 0, 0, 1, 0, 2, 0, *, * }      <
{ 0, 0, 1, 0, 1, *, *, * }      <
{ 0, 0, 0, *, *, *, *, * }      ?
{ 0, 0, 0, 1, *, *, *, * }      ?
{ 0, 0, 0, 1, 3, *, *, * }      ?
{ 0, 0, 0, 1, 3, 0, *, * }      ?
{ 0, 0, 0, 1, 3, 0, 0, * }      ?
{ 0, 0, 0, 1, 3, 0, 0, 0 }      <
{ 0, 0, 0, 1, 2, *, *, * }      ?
{ 0, 0, 0, 1, 2, 1, *, * }      ?
{ 0, 0, 0, 1, 2, 1, 1, * }      ?
{ 0, 0, 0, 1, 2, 1, 1, 0 }      <
{ 0, 0, 0, 1, 2, 1, 0, * }      <
{ 0, 0, 0, 1, 2, 0, *, * }      <
{ 0, 0, 0, 1, 1, *, *, * }      <
{ 0, 0, 0, 0, *, *, *, * }      <

Символы справа показывают отклик считающей части, сам перебор использует только данные о максимальном допустимом числе вхождений элементов и эти отклики, чтобы узнать, куда дальше.

Как у вас получилось на две строки меньше (97 vs. 99), удивительно.

-- Сб янв 27, 2018 03:00:56 --

А, так у вас в последнем посте другие числа; тогда имелся в виду тот, который пораньше. Сейчас сравню с новыми.

-- Сб янв 27, 2018 03:06:40 --

UPD. Позор мне, ещё больше разница получается (120 шагов):

Используется синтаксис Text

{ *, *, *, *, *, *, *, *, * }   ?
{ 1, *, *, *, *, *, *, *, * }   ?
{ 1, 1, *, *, *, *, *, *, * }   ?
{ 1, 1, 0, *, *, *, *, *, * }   ?
{ 1, 1, 0, 0, *, *, *, *, * }   ?
{ 1, 1, 0, 0, 0, *, *, *, * }   ?
{ 1, 1, 0, 0, 0, 1, *, *, * }   =
{ 1, 1, 0, 0, 0, 0, *, *, * }   ?
{ 1, 1, 0, 0, 0, 0, 1, *, * }   ?
{ 1, 1, 0, 0, 0, 0, 1, 1, * }   =
{ 1, 1, 0, 0, 0, 0, 1, 0, * }   <
{ 1, 1, 0, 0, 0, 0, 0, *, * }   ?
{ 1, 1, 0, 0, 0, 0, 0, 2, * }   ?
{ 1, 1, 0, 0, 0, 0, 0, 2, 1 }   =
{ 1, 1, 0, 0, 0, 0, 0, 2, 0 }   <
{ 1, 1, 0, 0, 0, 0, 0, 1, * }   <
{ 1, 0, *, *, *, *, *, *, * }   ?
{ 1, 0, 1, *, *, *, *, *, * }   ?
{ 1, 0, 1, 0, *, *, *, *, * }   ?
{ 1, 0, 1, 0, 1, *, *, *, * }   ?
{ 1, 0, 1, 0, 1, 0, *, *, * }   ?
{ 1, 0, 1, 0, 1, 0, 0, *, * }   ?
{ 1, 0, 1, 0, 1, 0, 0, 1, * }   =
{ 1, 0, 1, 0, 1, 0, 0, 0, * }   <
{ 1, 0, 1, 0, 0, *, *, *, * }   ?
{ 1, 0, 1, 0, 0, 1, *, *, * }   ?
{ 1, 0, 1, 0, 0, 1, 1, *, * }   ?
{ 1, 0, 1, 0, 0, 1, 1, 0, * }   ?
{ 1, 0, 1, 0, 0, 1, 1, 0, 1 }   =
{ 1, 0, 1, 0, 0, 1, 1, 0, 0 }   <
{ 1, 0, 1, 0, 0, 1, 0, *, * }   ?
{ 1, 0, 1, 0, 0, 1, 0, 2, * }   =
{ 1, 0, 1, 0, 0, 1, 0, 1, * }   <
{ 1, 0, 1, 0, 0, 0, *, *, * }   <
{ 1, 0, 0, *, *, *, *, *, * }   ?
{ 1, 0, 0, 1, *, *, *, *, * }   ?
{ 1, 0, 0, 1, 1, *, *, *, * }   ?
{ 1, 0, 0, 1, 1, 1, *, *, * }   ?
{ 1, 0, 0, 1, 1, 1, 0, *, * }   ?
{ 1, 0, 0, 1, 1, 1, 0, 0, * }   ?
{ 1, 0, 0, 1, 1, 1, 0, 0, 1 }   =
{ 1, 0, 0, 1, 1, 1, 0, 0, 0 }   <
{ 1, 0, 0, 1, 1, 0, *, *, * }   ?
{ 1, 0, 0, 1, 1, 0, 1, *, * }   ?
{ 1, 0, 0, 1, 1, 0, 1, 1, * }   ?
{ 1, 0, 0, 1, 1, 0, 1, 1, 1 }   =
{ 1, 0, 0, 1, 1, 0, 1, 1, 0 }   <
{ 1, 0, 0, 1, 1, 0, 1, 0, * }   <
{ 1, 0, 0, 1, 1, 0, 0, *, * }   <
{ 1, 0, 0, 1, 0, *, *, *, * }   ?
{ 1, 0, 0, 1, 0, 1, *, *, * }   ?
{ 1, 0, 0, 1, 0, 1, 1, *, * }   ?
{ 1, 0, 0, 1, 0, 1, 1, 2, * }   ?
{ 1, 0, 0, 1, 0, 1, 1, 2, 1 }   =
{ 1, 0, 0, 1, 0, 1, 1, 2, 0 }   <
{ 1, 0, 0, 1, 0, 1, 1, 1, * }   <
{ 1, 0, 0, 1, 0, 1, 0, *, * }   <
{ 1, 0, 0, 1, 0, 0, *, *, * }   <
{ 1, 0, 0, 0, *, *, *, *, * }   <
{ 0, *, *, *, *, *, *, *, * }   ?
{ 0, 1, *, *, *, *, *, *, * }   ?
{ 0, 1, 1, *, *, *, *, *, * }   ?
{ 0, 1, 1, 1, *, *, *, *, * }   ?
{ 0, 1, 1, 1, 0, *, *, *, * }   ?
{ 0, 1, 1, 1, 0, 0, *, *, * }   ?
{ 0, 1, 1, 1, 0, 0, 0, *, * }   ?
{ 0, 1, 1, 1, 0, 0, 0, 0, * }   ?
{ 0, 1, 1, 1, 0, 0, 0, 0, 1 }   =
{ 0, 1, 1, 1, 0, 0, 0, 0, 0 }   <
{ 0, 1, 1, 0, *, *, *, *, * }   ?
{ 0, 1, 1, 0, 1, *, *, *, * }   ?
{ 0, 1, 1, 0, 1, 0, *, *, * }   ?
{ 0, 1, 1, 0, 1, 0, 1, *, * }   ?
{ 0, 1, 1, 0, 1, 0, 1, 0, * }   ?
{ 0, 1, 1, 0, 1, 0, 1, 0, 1 }   =
{ 0, 1, 1, 0, 1, 0, 1, 0, 0 }   <
{ 0, 1, 1, 0, 1, 0, 0, *, * }   ?
{ 0, 1, 1, 0, 1, 0, 0, 2, * }   =
{ 0, 1, 1, 0, 1, 0, 0, 1, * }   <
{ 0, 1, 1, 0, 0, *, *, *, * }   ?
{ 0, 1, 1, 0, 0, 1, *, *, * }   ?
{ 0, 1, 1, 0, 0, 1, 1, *, * }   ?
{ 0, 1, 1, 0, 0, 1, 1, 1, * }   ?
{ 0, 1, 1, 0, 0, 1, 1, 1, 1 }   =
{ 0, 1, 1, 0, 0, 1, 1, 1, 0 }   <
{ 0, 1, 1, 0, 0, 1, 1, 0, * }   <
{ 0, 1, 1, 0, 0, 1, 0, *, * }   <
{ 0, 1, 1, 0, 0, 0, *, *, * }   <
{ 0, 1, 0, *, *, *, *, *, * }   ?
{ 0, 1, 0, 1, *, *, *, *, * }   ?
{ 0, 1, 0, 1, 1, *, *, *, * }   ?
{ 0, 1, 0, 1, 1, 1, *, *, * }   ?
{ 0, 1, 0, 1, 1, 1, 1, *, * }   =
{ 0, 1, 0, 1, 1, 1, 0, *, * }   ?
{ 0, 1, 0, 1, 1, 1, 0, 1, * }   ?
{ 0, 1, 0, 1, 1, 1, 0, 1, 1 }   =
{ 0, 1, 0, 1, 1, 1, 0, 1, 0 }   <
{ 0, 1, 0, 1, 1, 1, 0, 0, * }   <
{ 0, 1, 0, 1, 1, 0, *, *, * }   ?
{ 0, 1, 0, 1, 1, 0, 1, *, * }   ?
{ 0, 1, 0, 1, 1, 0, 1, 2, * }   ?
{ 0, 1, 0, 1, 1, 0, 1, 2, 1 }   =
{ 0, 1, 0, 1, 1, 0, 1, 2, 0 }   <
{ 0, 1, 0, 1, 1, 0, 1, 1, * }   <
{ 0, 1, 0, 1, 1, 0, 0, *, * }   <
{ 0, 1, 0, 1, 0, *, *, *, * }   <
{ 0, 1, 0, 0, *, *, *, *, * }   <
{ 0, 0, *, *, *, *, *, *, * }   ?
{ 0, 0, 1, *, *, *, *, *, * }   ?
{ 0, 0, 1, 1, *, *, *, *, * }   ?
{ 0, 0, 1, 1, 1, *, *, *, * }   ?
{ 0, 0, 1, 1, 1, 1, *, *, * }   ?
{ 0, 0, 1, 1, 1, 1, 1, *, * }   ?
{ 0, 0, 1, 1, 1, 1, 1, 2, * }   =
{ 0, 0, 1, 1, 1, 1, 1, 1, * }   <
{ 0, 0, 1, 1, 1, 1, 0, *, * }   <
{ 0, 0, 1, 1, 1, 0, *, *, * }   <
{ 0, 0, 1, 1, 0, *, *, *, * }   <
{ 0, 0, 1, 0, *, *, *, *, * }   <
{ 0, 0, 0, *, *, *, *, *, * }   <
[20, 18, 5], [20, 18, 3, 2], [20, 18, 2, 2, 1], [20, 14, 7, 2], [20, 14, 5, 3, 1], [20, 14, 5, 2, 2], [20, 10, 7, 5, 1], [20, 10, 7, 3, 2, 1], [20, 10, 5, 3, 2, 2, 1], [18, 14, 10, 1], [18, 14, 7, 3, 1], [18, 14, 7, 2, 2], [18, 14, 5, 3, 2, 1], [18, 10, 7, 5, 3], [18, 10, 7, 5, 2, 1], [18, 10, 7, 3, 2, 2, 1], [14, 10, 7, 5, 3, 2, 2]

[grizzly]

B@R5uk в сообщении #1287685 писал(а):

И этот код выдаёт приблизительно вот такие результаты:

Не уверен, что я всё понимаю правильно, но мне показалось, что в приведенном листинге порядка четверти строк бесполезные (это не страшно), но когда я стал смотреть, как их проще всего избежать, заметил в самом начале пропущенное решение:
1110000011

По поводу лишних строк пример. Если есть строка с ведущей единицей и она меньше целевого значения, то дальше играть на понижение нет смысла. Например, вот этот переход:
1000000110 -> 33 (43)
0000001010 -> 28 (43)
Просто лишний. Думаю, что в таких случаях нужно заменять первую (слева направо) комбинацию 001 на 110. То есть после 1000000110 должно идти 0000011010. Нужно, конечно, посмотреть аккуратней, но оптимизироваться там есть куда. А вот пропущенные решения это плохо.

[arseniiv]

grizzly в сообщении #1287706 писал(а):

заметил в самом начале пропущенное решение:
1110000011

Да, странно, указанных решений 16, но внизу написано, что найдено 22. Если считать найденные у меня, считая две двойки разными, получится именно 22. Интересно, где же его тогда зажевало.

[grizzly]

arseniiv в сообщении #1287698 писал(а):

ещё больше разница получается (120 шагов):

Я думаю, что это только из-за более подробного листинга.

[B@R5uk]

grizzly в сообщении #1287706 писал(а):

заметил в самом начале пропущенное решение:
1110000011

arseniiv в сообщении #1287709 писал(а):

Да, странно, указанных решений 16, но внизу написано, что найдено 22.

Это всё потому, что решения начинающиеся на несколько единичек обнаруживаются внутри тела кода, осуществляющего пропуск целой пачки решений. Они учитываются, но не отображаются, поскольку для отображения потребовался бы вложенный цикл для установки первых элементов в единички, а потом в нолики. Вот код, отвечающий за пропуски:

Используется синтаксис Java

                                if (0 < index) {
                                        totalSum = cumulativeSums[index] + sum;
                                        if (value >= totalSum) {
                                                if (value == totalSum) {
                                                        ++matchCount;
                                                }
                                                indices[0] = lastIndex;
                                                ++undershotsCount;
                                                undershotSkips += (1 << index + 1) - 2;
                                                index = 0;
                                                continue;
                                        }
                                }
 

Для упомянутого решения подмножество соседних комбинаций будет выглядеть так:
0010000011
0110000011
1110000011
1010000011
0100000011
1100000011
1000000011
Их все перебирать нет смысла, поскольку только полная сумма всех элементов даст попадание. Поэтому я исключил перебор таких случаев точно так же, как исключил перебор суммарных недолётов.

Вообще, вывод, выдаваемый моей программой надо воспринимать не как конечный результат, а как трассировку процесса её работы. Разумеется, когда алгоритм будет реализовываться по назначению, придётся добавить код, в том числе вложенный цикл, который будет выдавать ответ из пропущенной части, а не просто подсчитывать, что он есть.

arseniiv в сообщении #1287698 писал(а):

UPD. Позор мне, ещё больше разница получается (120 шагов):

Возможно, это как раз из-за того, что я сделал описанную только что оптимизацию. С другой стороны, трудоёмкость разных шагов (в том числе в разных программах) может очень сильно отличаться, так что число шагов не самый надёжных показатель.

arseniiv в сообщении #1287698 писал(а):

Вот какой протокол у моей наконец-то допиленной программы на ваших данных из спойлера (слагаемые также идут от больших к меньшим, но не повторяются):

Здорово! Она даже имеет оптимизацию по повторениям! Я пока над этим даже не думал.

grizzly в сообщении #1287706 писал(а):

Например, вот этот переход:
1000000110 -> 33 (43)
0000001010 -> 28 (43)
Просто лишний. Думаю, что в таких случаях нужно заменять первую (слева направо) комбинацию 001 на 110.

Вот это спорный вопрос. Такого рода подход потребует введения вложенного цикла, который будет частично дублировать функции основного цикла. Концептуально, на мой взгляд, это очень плохо. В плане ускорения вычислений, возможно, будут улучшения. Но первоочередной оптимизацией, как мне кажется, сейчас является учёт повторяющихся элементов. Это позволит заменить экспоненциальный множитель по числу повторений на линейный, а это очень сильное ускорение.

[B@R5uk]

Привёл код программы к виду, больше похожему на конечный продукт:

Используется синтаксис Java

import java.util.*;

public class StudySubsetSearch11 {
        
        private static final Random rng = new Random();
        private static final int maxRand = 20;
        private static final int size = 10;
        private static final int[] values = new int[size];
        
        private static SubsetsFinder finder;
        
        public static void main(String[] args) {
                int n, sum, tagetSum, flag, matchCount;
                int[] array;
                for (n = 0; n < size; n++) {
                        values[n] = 1 + rng.nextInt(maxRand);
                }
                Arrays.sort(values);
                System.out.println(Arrays.toString(values));
                System.out.println();
                sum = 0;
                for (n = 0; n < size; n++) {
                        sum += values[n];
                }
                tagetSum = sum / 3 + rng.nextInt(maxRand);
                finder = new SubsetsFinder(values, tagetSum);
                matchCount = 0;
                while (true) {
                        array = finder.findNext();
                        if (null == array) {
                                break;
                        }
                        sum = 0;
                        for (n = 0; size > n; ++n) {
                                flag = array[n];
                                sum += flag * values[n];
                                System.out.print(flag);
                        }
                        System.out.print(" -> ");
                        System.out.println(sum);
                        ++matchCount;
                }
                array = new int[size];
                System.out.println();
                System.out.print("Match count: ");
                System.out.println(matchCount);
        }
}

Используется синтаксис Java

import java.util.*;

public class SubsetsFinder {
        private int size, tagetSum, sum, index;
        private int[] values, cumulativeSums;
        private int[] entryFlags, indices;
        private boolean isDone;
        
        public SubsetsFinder(int[] values, int tagetSum) {
                size = values.length;
                this.tagetSum = tagetSum;
                sum = 0;
                index = size;
                this.values = Arrays.copyOf(values, size);
                cumulativeSums = new int[size];
                for (int n = 1; size > n; ++n) {
                        sum += values[n];
                        cumulativeSums[n] = sum;
                }
                sum = 0;
                entryFlags = new int[size];
                indices = new int[size];
                isDone = false;
        }
        
        public int[] findNext() {
                int n, lastIndex, totalSum;
                int[] result;
                boolean isSkipping, isActive;
                if (isDone) {
                        return null;
                }
                result = null;
                isActive = true;
                while (isActive) {
                        if (tagetSum < sum) {
                                isSkipping = true;
                        } else if (tagetSum == sum) {
                                isSkipping = true;
                                isActive = false;
                                result = Arrays.copyOf(entryFlags, size);
                        } else {
                                isSkipping = false;
                        }
                        if (0 == index) {
                                index = indices[0];
                                if (size == index) {
                                        isDone = true;
                                        isActive = false;
                                        continue;
                                }
                                lastIndex = indices[index];
                                entryFlags[index] = 0;
                                sum -= values[index];
                                --index;
                                if (0 < index) {
                                        totalSum = cumulativeSums[index] + sum;
                                        if (tagetSum >= totalSum) {
                                                if (tagetSum == totalSum) {
                                                        isActive = false;
                                                        result = Arrays.copyOf(entryFlags, size);
                                                        for (n = 1; index >= n; ++n) {
                                                                result[n] = 1;
                                                        }
                                                }
                                                indices[0] = lastIndex;
                                                index = 0;
                                                continue;
                                        }
                                }
                                indices[index] = lastIndex;
                                entryFlags[0] = 0;
                                sum -= values[0];
                                entryFlags[index] = 1;
                                sum += values[index];
                                continue;
                        }
                        if (isSkipping) {
                                lastIndex = indices[index];
                                entryFlags[index] = 0;
                                sum -= values[index];
                        } else {
                                lastIndex = index;
                        }
                        --index;
                        indices[index] = lastIndex;
                        entryFlags[index] = 1;
                        sum += values[index];
                }
                return result;
        }
}

Результат работы получается какой-то такой:

Используется синтаксис Text

[5, 6, 7, 14, 14, 14, 15, 16, 19, 19]

0100000111 -> 60
0010001011 -> 60
1100010101 -> 60
1100100101 -> 60
1101000101 -> 60
1010011001 -> 60
1010101001 -> 60
1011001001 -> 60
0110110001 -> 60
0111010001 -> 60
0111100001 -> 60
1100010110 -> 60
1100100110 -> 60
1101000110 -> 60
1010011010 -> 60
1010101010 -> 60
1011001010 -> 60
0110110010 -> 60
0111010010 -> 60
0111100010 -> 60
1111110000 -> 60

Match count: 21

Видно, что из-за повторяющихся элементов появляется множество повторяющихся решений. С этим надо срочно что-то делать. Осталось придумать, то именно...

[grizzly]

B@R5uk в сообщении #1287746 писал(а):

С этим надо срочно что-то делать. Осталось придумать, то именно...

Попросить у arseniiv алгоритм? Подозреваю, что он во всех отношениях оптимален.

[mustitz]

Привёл алгоритм Д. Кнута в более читаемый вид :)

Используется синтаксис C

#include <stdio.h>

#define CAPACITY 7

enum status { ACCEPTED, REJECTED };

struct state
{
    int free_space;
    const int * const item_weight_list;
};

static inline enum status include(struct state * restrict const me, const int index)
{
    const int item_weight = me->item_weight_list[index];
    if (me->free_space < item_weight) {
        return REJECTED;
    }

    me->free_space -= item_weight;
    return ACCEPTED;
}

static inline void exclude(struct state * restrict const me, const int index)
{
    const int item_weight = me->item_weight_list[index];
    me->free_space += item_weight;
}

static inline enum status swap(struct state * restrict const me, const int add_index, const int sub_index)
{
    const int add_weight = me->item_weight_list[add_index];
    const int sub_weight = me->item_weight_list[sub_index];
    const int delta = add_weight - sub_weight;
    if (me->free_space < delta) {
        return REJECTED;
    }

    me->free_space -= delta;
    return ACCEPTED;
}

void visit(struct state * restrict const me, const int len, const int * const combination)
{
    printf("[ ");
    for (int i=0; i<len; ++i) {
        printf("%d ", combination[i]);
    }
    printf("] uses %d\n", CAPACITY - me->free_space);
}

void enumerate(void * restrict const state, const int n)
{
    int t = 0;
    int c[n+1];
    c[0] = n;

    for (;;) {
        visit(state, t, c+1);

        if (c[t] > 0 && include(state, 0) == ACCEPTED) {
            c[++t] = 0;
            continue;
        }

        for (;;) {
            if (t==0) {
                return;
            }

            if (c[t-1] > c[t] + 1 && swap(state, c[t] + 1, c[t]) == ACCEPTED) {
                c[t] = c[t] + 1;
                break;
            }

            exclude(state, c[t--]);
        }
    }
}

int main()
{
    const int weight_list[] = { 1, 2, 3, 4, 5 };
    struct state state = { CAPACITY, weight_list };
    enumerate(&state, 5);
    return 0;
}