Problem plecakowy (knapsack problem) przy użyciu brute force o złożoności pamięciowej O(n)

Hej, w ramach mini-projektu uczelnianego muszę napisać program rozwiązujący problem plecakowy. Jako odpowiedź powinien zostać wypisany wektor składający się z n bitów, gdzie i-ty bit 1 oznacza włożenie i-tego przedmiotu do plecaka.

Znalazłem takie rozwiązanie:

static int max(int a, int b) {
        return (a > b) ? a : b;
    }

    static int knapSack(int capacity, int tabOfWeights[], int tabOfValues[], int numberOfItems) {

        if (numberOfItems == 0 || capacity == 0)
            return 0;

        if (tabOfWeights[numberOfItems - 1] > capacity)
            return knapSack(capacity, tabOfWeights, tabOfValues, numberOfItems - 1);

        else
            return max(tabOfValues[numberOfItems - 1] + knapSack(capacity - tabOfWeights[numberOfItems - 1], tabOfWeights,
                            tabOfValues, numberOfItems - 1),
                    knapSack(capacity, tabOfWeights, tabOfValues, numberOfItems - 1));
    }

Macie pomył jak wyłuskać z podzbiorów sumy i wartości indeksów? Suma do sprawdzenia, czy jest maksymalna a indeksy do utworzenia wektora charakterystycznego.

No to musisz do swojej funkcji rekurencyjnej przekazywać aktualny prefiks tego wektora.

Jeżeli uda ci się rozwiązać problem z tematu i to jeszcze rekurencją, przy zachowaniu O(n) to dostaniesz pierwszego informatycznego nobla w historii.

Już bardziej serio, spróbuj podejść do rozwiązywania każdego problemu od początku, czyli jak piszesz funkcję, która ma coś zrobić, to zacznij od zdefiniowania tego co ta funkcja ma zwracać, żeby rozwiązać problem. Pytania pomocnicze:

• Czy pojedynczy int daje ci wiedzę o czymkolwiek więcej niż "udało się zapakować 5 przedmiotów"? Czy gdybyś zwracał ten końcowy rekord w postaci boolean[], byłbyś w stanie odpowiedzieć na pytanie z problemu?
• Czy licząc jedynki w nim byłbyś w stanie wyciągnąć wartość potrzebną ci w algorytmie?