Застрял на внесении небольшой корректировки в алгоритм DP (счет для тай-брейка)

Question

Пример ввода:

45 8 4 10 44 43 12 9 8 2

Первое число = N

Второе число = T

Следующие цифры T = Набор значений

Myработа состоит в том, чтобы найти подмножество, в котором сумма является максимально возможной из всех подмножеств, которая не превышает N. Выведите этот набор и сумму.Таким образом, выходные данные для этого ввода будут:

2 8 9 12 10 4 sum:45

Моя проблема в том, что мне нечего выбирать между таймбрейкерами.Фактором разрыва связи будет набор с большим количеством элементов.Моя программа печатает это:

2 43 sum:45 

Вот код (стандартный ввод / вывод):

        int val = reader.nextInt();
        int num = reader.nextInt(); // never exceeds 20
        int[] cost = new int[20]; 
        int[][] dp = new int[10000][10000]; 
        int[][] path = new int[10000][10000];
        for (int i = 0; i < num; i++) {
            cost[i] = reader.nextInt();
        }
        for (int i = 0; i < num; i++) {
            for (int j = 0; j <= val; j++) {
                if (j < cost[i]) {
                    dp[i + 1][j] = dp[i][j];
                }
                else {
                    if (dp[i][j] < dp[i][j - cost[i]] + cost[i]) {
                        path[i+1][j] = 1;
                        dp[i + 1][j] = dp[i][j - cost[i]] + cost[i];
                    }
                    else {
                        dp[i + 1][j] = dp[i][j];
                    }
                }
            }
        }
        int k = val;
        for (int i = num; i >= 1; i--) {
            if (path[i][k] == 1 && k >= 0) {
                System.out.print(cost[i - 1] + " ");
                k = k - cost[i - 1];
            }
        }
        System.out.print("sum:" + dp[num][val] + '\n');

Answer 1

Вы находитесь на правильном пути с вашим двумерным массивом T x N. Но вы не должны отслеживать накопленную стоимость как значение каждой ячейки, которая уже отслеживается по 2-му индексу (j в вашем случае). Вместо этого отследите максимальное количество элементов, которое вы можете суммировать, чтобы получить к этой стоимости пока . Делая это, вам даже не нужен массив путей.

Представьте себе сценарий, где N = 5, T = 4, а числа: {4, 1, 1, 3}. Первый столбец будет отслеживать 1 в строке j == 4 и 0 везде. Второй столбец будет отслеживать 2 в строке j == 5, 1 в строках j == 4 и j == 1 и 0 везде. Вы могли бы заполнить это чем-то вроде этого (может понадобиться немного подправить ...):

dp[0][cost[0]] = 1;
for (int i = 1; i < T; i++) {

    dp[i][cost[i]] = 1;

    for (int j = N - 1; j >= 0; j--) {
        if (j >= cost[i] && dp[i-1][j-cost[i]] > 0) {
            dp[i][j] = dp[i-1][j-cost[i]] + 1;
        }
        dp[i][j] = Math.max(dp[i][j], dp[i-1][j]);
    }
}

Таблица dp в конце будет выглядеть так:

Sum (j)
     5 |    0    2    2    3
     4 |    1    1    1    2
     3 |    0    0    0    1
     2 |    0    0    2    2
     1 |    0    1    1    1
     0 |    0    0    0    0
______________________________
  cost |  { 4    1    1    3 }

Из этой таблицы вы знаете, что максимальное количество элементов, которое вы можете использовать для суммирования до 5, равно 3. Чтобы узнать, что это за элементы, вернитесь назад к dp[3][5]. Начиная с dp[2][5] != dp[3][5], вы должны добавить cost[3] (3) в качестве третьего элемента, поэтому добавьте 3 к вашему набору результатов. Следующее значение для проверки - dp[2][5 - cost[3]] или dp[2][2]. Сравните это с ячейкой слева, dp[1][2]. Они не равны, поэтому вы, должно быть, также добавили cost[2] (если они были равны, это означает, что вы не добавили cost[2], и следующая ячейка для проверки будет dp[1][2]). Продолжайте до dp[i][j] == 0 или i == 0, чтобы построить свой набор результатов.