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

Pytanie - CanSum

VPS Starter Arubacloud
0 głosów
228 wizyt
pytanie zadane 22 stycznia 2023 w C i C++ przez Dani Obywatel (1,420 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ź 22 stycznia 2023 przez mokrowski Mędrzec (155,460 p.)
Za każdym razem przesyłasz kopię mapy a nie referencję do niej.
komentarz 22 stycznia 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
Dokładnie i złożonnośc ci bardzo spada
komentarz 22 stycznia 2023 przez Dani Obywatel (1,420 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 22 stycznia 2023 przez pasjonat_algorytmiki Pasjonat (19,540 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 22 stycznia 2023 przez Dani Obywatel (1,420 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 22 stycznia 2023 przez Great Stary wyjadacz (12,300 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 22 stycznia 2023 przez mokrowski Mędrzec (155,460 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ź 117 wizyt
pytanie zadane 22 kwietnia 2022 w C i C++ przez polandonion Mądrala (6,970 p.)
0 głosów
1 odpowiedź 202 wizyt
pytanie zadane 31 sierpnia 2020 w C i C++ przez p4wix Obywatel (1,040 p.)
0 głosów
2 odpowiedzi 372 wizyt
pytanie zadane 15 lutego 2016 w C i C++ przez Kazik98x Obywatel (1,780 p.)

92,452 zapytań

141,262 odpowiedzi

319,085 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

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

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...