Блог

Я застрял на этой проблеме.

Задан массив чисел. На каждом шаге мы можем выбрать число, подобное N, в этом массиве и суммировать N с другим числом, существующим в этом массиве. Мы продолжаем этот процесс, пока все числа в этом массиве не будут равны нулю. Какое минимальное количество шагов требуется? (Мы можем гарантировать, что изначально сумма чисел в этом массиве равна нулю).

Пример: -20, -15,1,3,7,9,15

• Шаг 1: выберите -15 и суммируйте с 15 -> -20,0,1,3,7,9,0
• Шаг 2: выберите 9 и суммируйте с -20 -> -11,0,1,3,7,0,0
• Шаг 3: выберите 7 и суммируйте с -11 -> -4,0,1,3,0,0,0
• Шаг 4: выберите 3 и суммируйте с -4 -> -1,0,1,0,0,0,0
• Шаг 5: выберите 1 и суммируйте с -1 -> 0,0,0,0,0,0,0

Итак, ответ в этом примере равен 5.

Я пробовал использовать жадный алгоритм. Это работает следующим образом:

На каждом шаге мы выбираем максимальное и минимальное число, которое уже доступно в этом массиве, и суммируем эти два числа, пока все числа в этом массиве не будут равны нулю.

но это не работает и дает мне неправильный ответ. Кто-нибудь может помочь мне решить эту проблему?

 #include <bits/stdc  .h>

using namespace std;

int a[] = {-20,-15,1,3,7,9,15};

int bruteforce(){
    
    bool isEqualToZero = 1;
    for (int i=0;i<(sizeof(a)/sizeof(int));i  )
        if (a[i] != 0){
            isEqualToZero = 0;
            break;
        }
        
    if (isEqualToZero)
        return 0;
    int tmp=0,m=1e9;
    
    for (int i=0;i<(sizeof(a)/sizeof(int));i  ){
        for (int j=i 1;j<(sizeof(a)/sizeof(int));j  ){
            if (a[i]*a[j] >= 0) continue;
            tmp = a[j];
            a[i]  = a[j];
            a[j] = 0;
            
            m = min(m,bruteforce());
            
            a[j] = tmp;
            a[i] -= tmp;
        }
    }
    
    return m 1;
}

int main()
{
    cout << bruteforce();
}
 

Это подход грубой силы, который я написал для этой проблемы. Есть ли какой-либо алгоритм для более быстрого решения этой проблемы?

Это имеет np-полное ощущение, но следующий поиск выполняет поиск A * по всем возможным нормализованным частичным суммам на пути к одному ненулевому члену. Это решает вашу проблему и означает, что вы не попадаете в бесконечный цикл, если сумма не равна нулю.

Если жадность работает, сначала будет изучен жадный путь, убедитесь, что вы не можете сделать лучше, и вернитесь довольно быстро. Если жадность не работает, это может…займет намного больше времени.

Реализация на Python, потому что это легко для меня. Перевод на другой язык — это упражнение для читателя.

 import heapq

def find_minimal_steps (numbers):
    normalized = tuple(sorted(numbers))
    seen = set([normalized])
    todo = [(min_steps_remaining(normalized), 0, normalized, None)]

    while todo[0][0] < 7:
        step_limit, steps_taken, prev, path = heapq.heappop(todo)
        steps_taken = -1 * steps_taken # We store negative for sort order
        if min_steps_remaining(prev) == 0:
            decoded_path = []
            while path is not None:
                decoded_path.append((path[0], path[1]))
                path = path[2]
            return steps_taken, list(reversed(decoded_path))
        prev_numbers = list(prev)
        for i in range(len(prev_numbers)):
            for j in range(len(prev_numbers)):
                if i != j:
                    # Track what they were
                    num_i = prev_numbers[i]
                    num_j = prev_numbers[j]

                    # Sum them
                    prev_numbers[i]  = num_j
                    prev_numbers[j] = 0

                    normalized = tuple(sorted(prev_numbers))
                    if (normalized not in seen):
                        seen.add(normalized)
                        heapq.heappush(todo, (
                            min_steps_remaining(normalized)   steps_taken   1,
                            -steps_taken - 1, # More steps is smaller is looked at first
                            normalized,
                            (num_i, num_j, path)))

                    # set them back.
                    prev_numbers[i] = num_i
                    prev_numbers[j] = num_j

print(find_minimal_steps([-20,-15,1,3,7,9,15]))
 

Для развлечения я также добавил реализацию связанного списка, которая не просто сообщает вам, сколько минимальных шагов, но и какие из них он нашел. В этом случае его шаги (-15, 15), (7, 9), (3, 16), (1, 19), (-20, 20) означали добавление 15 к -15, от 9 до 7, от 16 до 3, от 19 до 1 и от 20 до -20.