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

Question

Учитывая набор функций f1 ... fn (дискретное время) и ограничение по времени (int), следует найти максимальный выходной сигнал, то есть распределить время по различным функциям, чтобы максимизировать сумму выходов используемых функций.

Для любой функции значение в любое время представляет собой общий выход функции, если она используется в течение указанного времени. то есть F (2) = общий выход функции, если используется в течение 2 секунд. НЕ F (1) + F (2).

Все значения (время, функциональные выходы) являются целыми числами.

Мой текущий алгоритм находит максимальное из возможных повреждений, проверяя F (t) для случая, когда все время было вложено в одну функцию, сравнивает это максимальное с максимальным из всех возможных выходов из предыдущего максимального M (t- 1) + добавление 1 секунды к каждой возможной функции (с записью уже использованных функций и времени).

public int computeDamage () {

    int totalTime = calculator.getTotalTime();
    int numAttacks = calculator.getNumAttacks();

    if(totalTime == 0) return 0;

    int[] attackHist = new int[numAttacks];

    return maxDamage(numAttacks, attackHist, 1, totalTime, 0);

}

public int maxDamage(int numAttacks, int[] attackHist, int start, int end, int max) {
    //get the max of all the values at f(start), save the attack
    int maxF = -1, attack = -1;
    for(int i = 0; i < numAttacks; i++) {
        int dam = calculator.calculateDamage(i, start);
        if(dam > maxF) {
            maxF = dam;
            attack = i;
        }
    }

    //if start isn't 1, get the max of all possible values added to the attackHist
    int maxH = -1, attackH = -1;
    if(start > 1) {
        for(int j = 0; j < numAttacks; j++) {
            int dChange = -1;
            if(attackHist[j] > 0) dChange = calculator.calculateDamage(j, attackHist[j]+1) - calculator.calculateDamage(j, attackHist[j]);
            else dChange = calculator.calculateDamage(j, attackHist[j]+1);

            if((max + dChange) > maxH) {
                maxH = max + dChange;
                attackH = j;
            }
        }

        //if max is greater, reset attackHist. Otherwise, add 1 to used attack
        if(maxF > maxH) {
            Arrays.fill(attackHist, 0);
            attackHist[attack] = start;
            max = maxF;
        } else {
            attackHist[attackH]++;
            max = maxH;
        }

    } else {
        //just set the max to maxF
        max = maxF;
        attackHist[attack] = 1;

    }

    if(end == start) return max;
    else return maxDamage(numAttacks, attackHist, start+1, end, max);
}

Для ввода 12.in

20 12
0 3 4 7 9 12 12 14 15 15 17 19
2 5 6 9 11 12 15 15 16 19 21 22
1 4 6 8 9 11 13 14 16 18 21 22
1 4 4 4 5 5 6 8 9 11 12 14
0 3 4 5 7 10 12 13 15 17 20 20
1 3 5 5 8 10 10 12 14 15 16 18
1 1 3 5 7 8 10 11 11 13 14 16
1 1 2 2 2 3 6 7 10 11 11 12
1 3 5 5 7 7 8 11 11 12 14 16
0 1 4 5 6 9 10 11 12 12 15 18
3 5 5 7 8 10 12 12 14 15 15 16
3 5 6 9 12 12 13 14 15 18 21 21
1 2 3 4 7 9 10 12 12 15 18 18
3 4 5 7 8 10 12 13 13 16 17 20
3 5 7 7 10 11 14 16 17 18 21 23
0 1 4 7 7 8 10 12 13 13 14 16
2 3 3 6 8 9 12 15 17 18 20 21
0 2 3 3 6 8 9 10 13 15 17 17
1 2 4 7 9 9 9 11 14 14 17 19
3 5 6 7 10 11 12 12 13 16 17 19

Первая строка сообщает, сколько функций (20) и сколько времени (12 секунд), чтобы максимизировать вывод.

Каждая строка - это функция, определенная в диапазоне от 1 до 12 F (t), подробно описывающая, какой ущерб эта функция ПОЛНОСТЬЮ наносит до этой точки.

Вывод должен быть 31, но мой код выводит 30.

Answer 1

Я не буду пытаться отлаживать ваш код, но я сообщу вам точно, что он должен делать.

Что вам нужно сделать, это создать таблицу, по функциям, по времени,(best_value, time_this_function).С вашим входом вот эта таблица:

[[(0, 1), (3, 2), (4, 3), (7, 4), (9, 5), (12, 6), (12, 7), (14, 8), (15, 9), (15, 10), (17, 11), (19, 12)],
 [(2, 1), (5, 2), (6, 3), (9, 4), (11, 5), (12, 6), (15, 7), (17, 2), (18, 3), (21, 4), (23, 5), (24, 6)],
 [(2, 0), (5, 0), (6, 3), (9, 0), (11, 0), (13, 2), (15, 0), (17, 0), (19, 2), (21, 0), (23, 0), (25, 2)],
 [(2, 0), (5, 0), (6, 0), (9, 0), (11, 0), (13, 0), (15, 0), (17, 0), (19, 0), (21, 0), (23, 0), (25, 0)],
 [(2, 0), (5, 0), (6, 0), (9, 0), (11, 0), (13, 0), (15, 0), (17, 0), (19, 0), (21, 0), (23, 0), (25, 0)],
 [(2, 0), (5, 0), (6, 0), (9, 0), (11, 0), (13, 0), (15, 0), (17, 0), (19, 0), (21, 0), (23, 0), (25, 0)],
 [(2, 0), (5, 0), (6, 0), (9, 0), (11, 0), (13, 0), (15, 0), (17, 0), (19, 0), (21, 0), (23, 0), (25, 0)],
 [(2, 0), (5, 0), (6, 0), (9, 0), (11, 0), (13, 0), (15, 0), (17, 0), (19, 0), (21, 0), (23, 0), (25, 0)],
 [(2, 0), (5, 0), (6, 0), (9, 0), (11, 0), (13, 0), (15, 0), (17, 0), (19, 0), (21, 0), (23, 0), (25, 0)],
 [(2, 0), (5, 0), (6, 0), (9, 0), (11, 0), (13, 0), (15, 0), (17, 0), (19, 0), (21, 0), (23, 0), (25, 0)],
 [(3, 1), (5, 2), (8, 1), (10, 2), (12, 1), (14, 1), (16, 1), (18, 1), (20, 1), (22, 1), (24, 1), (26, 1)],
 [(3, 1), (6, 1), (8, 0), (11, 1), (13, 1), (15, 1), (17, 1), (20, 5), (22, 5), (24, 5), (26, 5), (28, 5)],
 [(3, 0), (6, 0), (8, 0), (11, 0), (13, 0), (15, 0), (17, 0), (20, 0), (22, 0), (24, 0), (26, 0), (28, 0)],
 [(3, 1), (6, 0), (9, 1), (11, 0), (14, 1), (16, 1), (18, 1), (20, 0), (23, 1), (25, 1), (27, 1), (29, 1)],
 [(3, 1), (6, 0), (9, 0), (12, 1), (14, 0), (17, 1), (19, 1), (21, 1), (23, 0), (26, 1), (28, 1), (30, 1)],
 [(3, 0), (6, 0), (9, 0), (12, 0), (14, 0), (17, 0), (19, 0), (21, 0), (23, 0), (26, 0), (28, 0), (30, 0)],
 [(3, 0), (6, 0), (9, 0), (12, 0), (14, 0), (17, 0), (19, 0), (21, 0), (23, 0), (26, 0), (28, 0), (30, 0)],
 [(3, 0), (6, 0), (9, 0), (12, 0), (14, 0), (17, 0), (19, 0), (21, 0), (23, 0), (26, 0), (28, 0), (30, 0)],
 [(3, 0), (6, 0), (9, 0), (12, 0), (14, 0), (17, 0), (19, 0), (21, 0), (23, 0), (26, 0), (28, 0), (30, 0)],
 [(3, 1), (6, 0), (9, 0), (12, 0), (15, 1), (17, 0), (20, 1), (22, 1), (24, 1), (26, 0), (29, 1), (31, 1)]]

И как только у вас есть эта таблица, вам нужно просто пройтись от последней записи назад, чтобы выяснить путь.

Время, проведенноедля каждой функции, от последней к первой:

(31, 1) => 1
(28, 0) => 0
(28, 0) => 0
(28, 0) => 0
(28, 0) => 0
(28, 1) => 1
(25, 1) => 1
(22, 0) => 0
(22, 5) => 5
(10, 2) => 2
(5, 0)  => 0
(5, 0)  => 0
(5, 0)  => 0
(5, 0)  => 0
(5, 0)  => 0
(5, 0)  => 0
(5, 0)  => 0
(5, 0)  => 0
(5, 2)  => 2
# At this point we back up out of our table, and we spent no time on the first.

в обратном порядке мы получаем 2 для второй функции, 2 для 11-й, 5 для 12-й, 1 в14-е, 1 на 15-м и 1 на последнем.

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