Z danej tablicy (zadzwoń do numeru [] ), chcę innej tablicy ( wyniki [] ), który zawiera wszystkie możliwości sumy między elementami pierwszej tablicy.

Na przykład, jeśli mam liczby [] = {1,3,5}, wyniki [] będą {1,3,5,4,8,9,0}. Istnieje 2 ^ n możliwości. Nie ma znaczenia, czy numer pojawia się dwa razy, ponieważ wyniki [] będą a A >.

Zrobiłem to na sumę par lub triplet i jest bardzo łatwe. Ale nie rozumiem, jak działa, gdy sumujemy 0, 1, 2 lub n liczb.

To właśnie zrobiłem dla par:

std::unordered_set<int> pairPossibilities(std::vector<int> &numbers) {
    std::unordered_set<int> results;
    for(int i=0;i<numbers.size()-1;i++) {
        for(int j=i+1;j<numbers.size();j++) {
            results.insert(numbers.at(i)+numbers.at(j));
        }
    }
    return results;
}

Ponadto, zakładając, że liczba [] jest sortowana, czy istnieje możliwość sortowania wyników [] podczas wypełnienia go?

Dzięki!

1
tuxikigo 5 czerwiec 2018, 12:19

4 odpowiedzi

Najlepsza odpowiedź

Po z dynamicznej odpowiedzi programowania można jechać z rekurencyjnym rozwiązaniem, a następnie użyć zapamiętywania do pamięci podręcznej, podejście do góry w przeciwieństwie do oddolnego AMIT.

vector<int> subsetSum(vector<int>& nums)
{
    vector<int> ans;
    generateSubsetSum(ans,0,nums,0);
    return ans;
}

void generateSubsetSum(vector<int>& ans, int sum, vector<int>& nums, int i)
{
    if(i == nums.size() )
    {
        ans.push_back(sum);
        return;
    }

    generateSubsetSum(ans,sum + nums[i],nums,i + 1);
    generateSubsetSum(ans,sum,nums,i + 1);
}

Result is : {9 4 6 1 8 3 5 0} dla zestawu {1,3,5}

To po prostu wybiera pierwszą liczbę przy pierwszym indeksie {x0}} dodaje go do sum i rejestruje. Po powrocie następuje druga gałąź, sum, bez dodanej nums[i]. Aby zapamiętać, że masz pamięć podręczną do przechowywania sum w i.

1
Samer Tufail 5 czerwiec 2018, 09:57

Można to zrobić za pomocą Dynamic Programming (DP) w O(n*W) gdzie {{x1 }}.

Jest to w zasadzie takiego samego rozwiązania Problem suma podzbioru, wykorzystując fakt, że problem ma optymalną podkonstrukcję .

DP[i, 0] = true
DP[-1, w] = false          w != 0
DP[i, w] = DP[i-1, w] OR DP[i-1, w - numbers[i]]

Zacznij, postępując zgodnie z powyższym rozwiązaniem, aby znaleźć DP[n, sum{numbers}].

W rezultacie otrzymasz:

DP[n , w] = true Jeśli i tylko wtedy, gdy w można skonstruować z numbers

2
amit 5 czerwiec 2018, 09:25

Zrobiłbym coś takiego (wydaje się łatwiejsze) [chciałem to umieścić w komentarzu, ale nie można napisać przesuwania i wyjmować Elem na raz - możesz potrzebować połączonej listy]

1 3 5
3 5
-----
4 8


1 3 5
5
-----
6

1 3 5
3 5
5
------
9

Dodaj 0 do listy w końcu.

Innym sposobem na rozwiązanie jest utworzenie tablic podzbiorów wektorowych elementów, a następnie podsumowują dane wektora każdej tablicy. na przykład 1 3 5 = {1, 3} + {1,5} + {3,5} + {1,3,5} Po usunięciu zestawów pojedynczego elementu.

Należy pamiętać, że zawsze łatwiej powiedzieć niż zrobione. Pojedynczy mały błąd wzdłuż realizowanego algorytmu zajmie dużo czasu, aby go znaleźć. =]]

1
Hello Everyone 5 czerwiec 2018, 10:00

Musi też być wersja binarna. Ten jest nieco ciężki i opiera się na tym zestawie odpowiedzi, które wspomniałeś, aby filtrować powtarzające się wyniki:

Split the list into 2,  
and generate the list of sums for each half 
  by recursion:
    the minimum state is either 
      2 entries, with 1 result, 
      or 3 entries with 3 results
      alternatively, take it down to 1 entry with 0 results, if you insist
Then combine the 2 halves:
  All the returned entries from both halves are legitimate results
  There are 4 additional result sets to add to the output result by combining:
    The first half inputs vs the second half inputs
    The first half outputs vs the second half inputs
    The first half inputs vs the second half outputs
    The first half outputs vs the second half outputs

Należy pamiętać, że wyjścia dwóch połówek mogą mieć wspólne elementy, ale powinny być traktowane oddzielnie dla tych kombajnów.
Wejścia można szorować od zwróconych wyjść każdej rekurencji, jeśli wejścia są uzasadnione końcowe wyniki. Jeśli są oni, mogą być dodawane z powrotem na etapie najwyższego poziomu lub zwrócone przez etap poziomu dolnego i nie pod uwagę ponownie w łączeniu.

Możesz użyć bitfield zamiast zestawu do filtrowania duplikatów. Istnieją rozsądnie skuteczne sposoby przejścia przez bitfield, aby znaleźć wszystkie zestawy. Maksymalny rozmiar bitfield jest sumą wszystkich wejść.

Nie ma tutaj inteligencji, ale wiele okazji do przetwarzania równoległego w rekurencji i łączy kroki.

1
Gem Taylor 5 czerwiec 2018, 10:18