Оптимизация ранца с 3 размеры


Постановка Задачи:

Я получил набор цен для \ФП\$ пунктов, которые я должен выяснить, что является максимальным значением я могу получить с \$М\$ деньги, выбрав именно \$с\$ пунктам, не превышая количество денег у меня. Очевидно, \$с \Лек Н\$.

Решение:

Код для вышеуказанной проблемы является разработанный с использованием предложений, взятых из здесь. Код в Java приведен ниже:

public class KnpMD {


    public static void main(String[] args) {

        int items[] = {4,6,9,10};
        int M = 12;
        int C = 2;

        int dp[][][] = new int[items.length+1][M+1][C+1];

        for(int i = 0; i < items.length+1; i++) {
            for(int j = 0; j < M+1; j++) {
                for(int k = 1; k <= C; k++) {
                    dp[i][j][k] = -1;
                }
            }
        }

        for(int i = 0; i < items.length; i++) {
            for(int j = 1 ; j < M + 1; j++) {

                for(int k = 1; k <= C; k++) {

                    dp[i+1][j][k] = dp[i][j][k];// to Copy all previous optimal states found.

                    if(items[i] > j)
                        continue;

                    if(dp[i][j-items[i]][k-1] != -1)
                        dp[i+1][j][k] = Math.max(dp[i+1][j][k],
                                dp[i][j-items[i]][k-1] + items[i]);
                }
            }


        }

        System.out.println(dp[items.length][M][C]);
    }
}

Какие улучшения я могу добавить в этот код? Я не могу следовать optimzations предложил в ответ, указанному выше.

Может кто подскажет, в чем смысл заявления(ссылка на ответ выше)

В предыдущие формулы, мы нашли оптимальное решение, которое состояла из не более чем (к−1)(к−1) элементов среди первых (к−1)(Ж−1) как TI,J−1,и к−1 Тим., J−1,и к−1. Однако должно быть ясно, что это точно равна maxp=0,так как J−1{ти,п}maxp=0,так как J−1{ті,п} только с помощью оригинальный стол!! т. е., оптимальное решение с не более чем на КК пользования можно также извлечь, рассматривая оптимальные решения с 1 предмет, 2 предмета, 3 предмета, ... (к−1)(к−1) элементов ...

Любые другие улучшения будут с благодарностью.



Комментарии