Не используете правильные идексы? - PullRequest
Новая
       29

Не используете правильные идексы?

0 голосов
/ 20 мая 2018

Я пытаюсь реализовать задачу о сумме подмножеств.Таким образом, основная идея состоит в том, что у нас есть контейнер с некоторой емкостью C, а также у нас есть стаканы с Capacity -c-, и мы хотели бы заполнить C ТОЧНО -C-литрами.Теперь позвольте мне показать вам, что я сделал.

* Я опущу класс container, поскольку он является объектом и на самом деле не влияет на сам алгоритм: 

public static int calcolaNumeroContenitori(int C, ArrayList<Contenitore> p)
    {

        boolean B[][] = new boolean[p.size()][C];
        boolean U[][] = new boolean[p.size()][C];

        B[0][0] = true; 
        U[0][0] = false;
        int num_cont = 0;
        int j;
        int i;
        //prima riga - caso base
        for( j = 0; j < C; j++)
        {
            if(j == p.get(0).getCapienza())
            {
                B[0][j] = true;
                U[0][j] = true;
             }
            else
            {
                B[0][j] = false;
                U[0][j] = false;
            }
        }
        //caso generale
        for(i = 1; i < p.size(); i++)
        {
            for(j = 0; j < C; j++)
            {
                if(j >= p.get(i).getCapienza())
                {
                    B[i][j] = B[i-1][j] || B[i-1][j - p.get(i).getCapienza()];
                    U[i][j] = B[i-1][j-p.get(i).getCapienza()];
               }
                else
                { 
                     B[i][j] = B[i-1][j];
                     U[i][j] = false;
                }
            }
        }

        if(!B[p.size()-1][C-1])
            {
                System.out.println("-1");
            }else
            {

                i = p.size()-1;
                j = C-1;
                while( i >= 0 && j >= 0)
                {
                    if(U[i][j])
                    {
                        num_cont++;
                        System.out.println("Usato: "+p.get(i).getId()
                                +" capienza:" + p.get(i).getCapienza());
                        j = j - p.get(i).getCapienza();
                    }
                    i--;
                }
             }
           return num_cont;


    }

, когда я запускаю это: 

    Contenitore c1 = new Contenitore("c1",1);
    Contenitore c2 = new Contenitore("c2",2);
    Contenitore c3 = new Contenitore("c3",3);



    lista_contenitori.add(c1);
    lista_contenitori.add(c2);
    lista_contenitori.add(c3);
    System.out.println(calcolaNumeroContenitori(4, lista_contenitori));

Я получаю в результате: 

Container: c2 capacity:2
Container: c1 capacity:1
2

, который не является правильным ответом.НО, если вы пытаетесь думать в Java, все начинается с 0. Я имею в виду, что, возможно, 4 на самом деле читается как 3 (0,1,2,3).Что именно мне здесь не хватает?

Спасибо!

1 Ответ

0 голосов
/ 20 мая 2018

Вы, очевидно, уже диагностировали проблему, но, возможно, не подробно.Проблема действительно в том, что самый высокий индекс в массиве на единицу меньше его длины.

В частности, ваша матрица должна включать позицию C, поэтому она должна иметь размерность C + 1.И, например, здесь: j = C-1; и здесь: B[p.size()-1][C-1] вы будете искать, можно ли достичь значения C - 1 путем сложения контейнеров, что, очевидно, на 1 меньше фактической цели.

...