Учитывая конечную последовательность натуральных чисел между [0-5], скажем, [0,3,1,5,2,4,4,4] и стартовой последовательностью [0,0,0,0,0,0,0,0].Теперь мы хотим построить нашу данную последовательность из начальной последовательности, выполняя пошаговые операции.За один шаг мы можем либо увеличить все числа из нашей стартовой последовательности на 1, либо увеличить только один индекс из этой последовательности на 1. Как только мы увеличим 5 в этом случае, он станет 0.
Что такоесамый эффективный способ найти решение, которое требует наименьшего количества шагов?Это решение должно, конечно, также применяться к другим входным данным (длина + верхняя граница).Для начальной последовательности мы можем предположить, что для каждого индекса это всегда 0.
Подход методом грубой силы может выглядеть следующим образом.
int upperBound = 5;
int[] endSequence = {0,3,1,5,2,4,4,4};
int currentBestSteps = Integer.MAX_VALUE;
int currentTimesIncreaseAll = 0;
for(int start = 0;start <= upperBound;start++){ //how many times to increase all
//counter how many steps required total, starting with start amount of steps
//since we increase all values 'start' times
int counterSteps = start;
//go through all end values and calc how many steps required
for(int end:endSequence){
if(start <= end){
counterSteps += end-start;
}else{
counterSteps += end+upperBound+1-start;
}
}
System.out.println("solution: increase all "+start+
" times, total steps: "+counterSteps);
if(counterSteps < currentBestSteps){
currentBestSteps = counterSteps;
currentTimesIncreaseAll = start;
}
}
System.out.println("best solution: increase all "+currentTimesIncreaseAll+
" times, total steps: "+currentBestSteps);
Результаты:
solution: increase all 0 times, total steps: 23
solution: increase all 1 times, total steps: 22
solution: increase all 2 times, total steps: 21
solution: increase all 3 times, total steps: 20
solution: increase all 4 times, total steps: 19
solution: increase all 5 times, total steps: 30
best solution: increase all 4 times, total steps: 19