• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Pytanie - CanSum

Aruba Cloud PRO i VPS, Openstack, VMWare, MS Hyper-V
0 głosów
65 wizyt
pytanie zadane 5 dni temu w C i C++ przez Dani Użytkownik (650 p.)
#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

int canSum(int TargetSum, vector<int> numbers,unordered_map<int,int> memo) {
	if (memo.find(TargetSum) != memo.end()) return memo[TargetSum];
	if (TargetSum == 0) return true;
	if (TargetSum < 0) return false;
	for (int x : numbers) {
		int remainder = TargetSum - x;
		if (canSum(remainder, numbers, memo)) {
			memo[TargetSum] = true;
			return true;
		}
	}
	memo[TargetSum] = false;
	return false;
}

int main()
{
	unordered_map<int, int> memo;
	/*cout << canSum(7, { 2,3 }, memo) << '\n';
	cout << canSum(7, { 5,3,4,7 }, memo) << '\n';
	cout << canSum(7, {2, 4 }, memo) << '\n';
	cout << canSum(8, {2,3,5}, memo) << '\n';*/
	cout << canSum(300, {7,14}, memo) << '\n';
}

Witam, napisałem kod, który powinien być szybszy i wykonywać ostatni element w szybszym czasie, używając mapy która przechowuje nam pewne wartości, jednak program nie wyświetla ostatniego zapytania zbyt szybko. Co mogłem przeoczyć?

1 odpowiedź

+2 głosów
odpowiedź 5 dni temu przez mokrowski Mędrzec (153,580 p.)
Za każdym razem przesyłasz kopię mapy a nie referencję do niej.
komentarz 5 dni temu przez pasjonat_algorytmiki Gaduła (4,190 p.)
Dokładnie i złożonnośc ci bardzo spada
komentarz 5 dni temu przez Dani Użytkownik (650 p.)
Panowie, uratowaliście mi życie! Dzięki wielkie.

Czy jak nie mam refernecji do vectora to też mu tutaj złożonośc spada?
komentarz 5 dni temu przez pasjonat_algorytmiki Gaduła (4,190 p.)
On go kopiuje całego wtedy.

Możesz albo wyciągnąc vector i mapę przed maina i wtedy masz globalny, najszybciej

Albo właśnie referencję przekazać.

W programowaniu konkursowym np. OI, OIJ, potyczki itp. zazwyczaj robi się większość globalnie, żeby się nie męczyć.
komentarz 5 dni temu przez Dani Użytkownik (650 p.)
Ej bo jednak sprawdzam jeszcze raz poprawność tego problemu, i wychodzi inny wynik gdy daję referencję niż kopiuję go. W czym może być problem?

Edit : Muszę clearować mapę po każdym pytaniu
komentarz 5 dni temu przez Great Stary wyjadacz (10,140 p.)

Takie tam prowizoryczne rozwiązanie:

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

int canSum(int TargetSum, const vector<int>& numbers, unordered_map<int, int>& memo) {
    if (memo.find(TargetSum) != memo.end()) return memo[TargetSum];
    if (TargetSum == 0) return true;
    if (TargetSum < 0) return false; 
    for (int x : numbers) {
        int remainder = TargetSum - x;
        if (canSum(remainder, numbers, memo)) {
            memo[TargetSum] = true;
            return true;
        }
    }

    memo[TargetSum] = false;
    return false;
}

int canSum(int TargetSum, const vector<int>& numbers) {
    unordered_map<int, int> memo;
    return canSum(TargetSum, numbers, memo);
}

int main()
{
    cout << canSum(7, { 2,3 }) << '\n';
    cout << canSum(7, { 5,3,4,7 }) << '\n';
    cout << canSum(7, {2, 4 }) << '\n';
    cout << canSum(8, {2,3,5}) << '\n';
    cout << canSum(300, { 7,14 }) << '\n';
}

Może warto zrezygnować z rekurencji.

komentarz 5 dni temu przez mokrowski Mędrzec (153,580 p.)
Jeśli chcesz mieć tę memoizację, to deklaruj mapę statycznie w funkcji. C++ gwarantuje inicjalizację jej przy pierwszym wejściu.

Podobne pytania

+1 głos
1 odpowiedź 93 wizyt
pytanie zadane 22 kwietnia 2022 w C i C++ przez polandonion Gaduła (4,640 p.)
0 głosów
1 odpowiedź 145 wizyt
pytanie zadane 31 sierpnia 2020 w C i C++ przez p4wix Obywatel (1,020 p.)
0 głosów
2 odpowiedzi 88 wizyt
pytanie zadane 15 lutego 2016 w C i C++ przez Kazik98x Obywatel (1,800 p.)

90,298 zapytań

138,894 odpowiedzi

311,080 komentarzy

60,012 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Sklep oferujący ćwiczenia JavaScript, PHP, rozmowy rekrutacyjne dla programistów i inne materiały

Oto dwie polecane książki warte uwagi. Pełną listę znajdziesz tutaj.

...