PROBLEMA C++| The Coin Change Problem

[Marcus Aseth]

Stavo provando a risolvere il problema del titolo, del quale potete leggere la spiegazione a questo link

Ecco il mio algoritmo:

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int allPermutation(const vector<int>& coins, int targetVal , int start = 0, int accumulated = 0);

int main() {
    //read data
    int targetVal,size;
    cin >> targetVal >> size;
  
    //build vector
    vector<int> coins(size);
    for(auto& c : coins){cin >> c;}
    sort(coins.begin(),coins.end());
  
    //ignore coins bigger than targetVal
    auto end = find_if(coins.begin(),coins.end(),[&targetVal](int i){ return i > targetVal;});
    int newSize = end - coins.begin();
    coins.resize(newSize);
 
    //find answer
    cout << allPermutation(coins,targetVal);
  
    return 0;
}

int allPermutation(const vector<int>& coins, int targetVal , int start, int accumulated)
{
    if(accumulated > targetVal){return 0;}
    if(accumulated == targetVal){return 1;}
 
    int answer{};
    for(int i = start; i < coins.size(); i++){
       answer += allPermutation(coins, targetVal, i, accumulated + coins[i]);
    }
    return answer;
}

Passo con successo 7 dei test case, ma gli altri 10 richiedono troppo tempo per completare...
Qualche suggerimento su dove potrei ottimizzare? :S

 

[Marcus Aseth]

Ho fatto una modifica all'algoritmo.

Adesso passo con successo 10 test case, ma ne fallisco 7 perchè continua ad impiegare troppo tempo... :D

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int allPermutation(const vector<int>& coins, int targetVal , int start = 0, int accumulated = 0);

int main() {
    //read data
    int targetVal,size;
    cin >> targetVal >> size;
 
    //build vector
    vector<int> coins(size);
    for(auto& c : coins){cin >> c;}
    sort(coins.begin(),coins.end());
 
    //find answer
    cout << allPermutation(coins,targetVal);
 
    return 0;
}

int allPermutation(const vector<int>& coins, int targetVal , int start, int accumulated)
{
    if(accumulated > targetVal){return -1;}
    if(accumulated == targetVal){return 1;}
 
    int answer{}, resoult{};
    for(int i = start; i < coins.size(); i++){
       resoult = allPermutation(coins, targetVal, i, accumulated + coins[i]);
       if(resoult == -1){
           //end early assuming a sorted vector. No point in adding bigger coins if
           //we already exceed targetVal with smaller ones
           break;
       }
        answer += resoult;
    }
    return answer;
}

 

[Marcus Aseth]

Dopo un pò di pratica con carta e matita, scrivendo tutte le possibili combinazioni, penso di aver trovato una pattern:

Spoiler: --

coins = {2 3 5 6}
combinationValue = {0 0 1 2}

targetVal = 10

6|2|2 val= 1+ (0+0)

5|5 val= 1+ (1)
5|3|2

3|3|2|2 val= 1+ (0+0)

2|2|2|2|2 val= 1+ (0+0+0+0)

combinations for targetVal = 5 possible combinations

come nell'esempio sopra, date le monete 2,3,5,6 assegno un valore chiamato combinationValue a ciascuna che è il numero di combinazioni delle altre monete più piccole che mi danno il valore di quella moneta (dato un certo set di monete).
A questo punto mi basta percorrere l'array di monete al contrario e trovare tutte le somme uguali a targetVal, e per ciascuna di esse aggiungere 1 (combinazione con la prima cifra) più il "combinationValue" di ciascuna cifra che segue.

Questa è l'intuizione, non sono sicuro sia davvero così, non mi resta che provare a tradurlo in un algoritmo e vedere se dà la risposta esatta :S
L'idea è di costruire una map<int,int> dalla cifrà più bassa in su, così ogni cifra che segue usa il combinationValue di quelle sotto per scoprire il numero di combinazioni possibili senza doverle provare una ad una.

EDIT: come non detto, sono totalmente sulla strada sbagliata, credo :D

 

[rodhellas]

Può aver senso fare le varie combinazioni usando il MIN, MAX dell'array e MID che sarebbe la posizione nell'array della metà del valore da trovare (es n=10 -> 5)? (Secondo me è una boiata ma tant'è).
Oppure per ogni valore che si prende nella combinazione si sposta il MAX all'elemento più grande < del valore da trovare meno il valore trovato ( [1,2,3,4] e n=4; prendo 1 e ottengo [1,2,3,4], se prendo uno avanti cosi, se passo a due: ottengo [1,2,3,4], quindi l'unico elemento che potrò prendere sarà 1)

 

[Marcus Aseth]

Può aver senso fare le varie combinazioni usando il MIN, MAX dell'array e MID che sarebbe la posizione nell'array della metà del valore da trovare (es n=10 -> 5)? (Secondo me è una boiata ma tant'è).
Oppure per ogni valore che si prende nella combinazione si sposta il MAX all'elemento più grande < del valore da trovare meno il valore trovato ( [1,2,3,4] e n=4; prendo 1 e ottengo [1,2,3,4], se prendo uno avanti cosi, se passo a due: ottengo [1,2,3,4], quindi l'unico elemento che potrò prendere sarà 1)

Una cosa che penso di aver capito è che non fà a risolverlo bruteforce tramite molte iterazioni, perchè se prendi il set

5 37 8 39 33 17 22 32 13 7 10 35 40 2 43 49 46 19 41 1 12 11 28

ed il valore target è 166, hai ben 96.190.959 di combinazioni possibili (questo è uno dei test nei quali il mio primo algoritmo impiega troppo tempo per completarlo)

 

[rodhellas]

Credo che sia come la tua intuizione di prima

 

[Marcus Aseth]

Forse l'intuizione era corretta, ma ci sono alcuni problemi...prendiamo ad esempio questo set che ho inventato ed ho "scansionato" attraverso il mio algoritmo originale (lento ma corretto), a quanto pare ci sono 17 combinazioni possibili se si cerca di creare il numero 14 usando i numeri in quel set.
Ho provato a trovarle a mano, ecco il risultato

---------coins ={2 3 4 5 9 10}
combinationVal ={1 1 2 2 2  3}
targetVal = 14
CorrectAnswer = 17 combinations


targetVal = 14

10 4        val= 3 * 2 = 6
5 5 4
2 2 2 2 2 4
10 2 2
5 5 2 2
2 2 2 2 2 2 2


9 5         val= 2 * 2 = 4
3 3 3 5
9 3 2
3 3 3 3 2

4 4 4 2     val= 1 + 3
4 4 2 2 2
4 2 2 2 2 2
2 2 2 2 2 2 2

4 4 3 3     val= 1 + 2
4 2 2 3 3
2 2 2 2 3 3

myAnswer =  17 combinations

Quindi da quel che vedo, pare funzionare se inizio assegnando un "combinationVal" di 1 a ciascun valore nel set di input, poi aumento di 1 il combinationVal per quei numeri nel set più piccoli di targetVal che possono essere ottenuti moltiplicando fra loro altri due numeri del set, per esempio il 10 ha un combinationVal di 3 perchè si può ottenere tramite 10, 5x2, 2x5 e quindi 10, 5 5, 2 2 2 2 2 che sono 3 differenti valide combinazioni di "monete".
Percui dove posso inserire un 10, sò di poter inserire 3 combinazioni diverse.
Di conseguenza non devo neppure iterare manualmente tutte le combinazioni che iniziano con 5 o con un 2, perchè il 10 è più piccolo di targetVal ed include gia tutte quelle combinazioni.
Però come si vede in alto, non sono ancora sicuro di come comportarmi nel caso di combinazioni che hanno più di una cifra come 4 4 4 2 e 4 4 3 3.
Posso elencarle manualmente ed ottenere il risultato corretto, ma non ho ben chiaro quale sia la formula matematica per capire il numero di combinazioni.
Mentre nel caso di

10 4        val= 3 * 2 = 6

mi basta moltiplicare tra loro i combinationVal associati alle 2 cifre, con 4 4 4 2 mi uscirebbe 8 combinazioni, il che è falso...
Vuol dire che se ho più di due cifre, devo moltiplicare i combinationVal di quelle uniche diverse tra loro e poi aggiungere 1 per ogni cifra che si ripete?
quindi
4 4 4 2 val = (2 * 1) + 1 + 1
4 4 3 3 val = (2 * 1) + 1
...In questo modo ottengo la risposta giusta, ma con solo questo esempio davanti, non posso dire se sto forzando la risposta che voglio sui numeri che ho o se sia davvero la soluzione corretta... x_x
Magari invece devo moltiplicare i combinationVal delle cifre uniche e poi aggiungere il (combinationVal - 1) per quelle che si ripetono, nel caso qui del 4 quindi aggiungo sempre 1 ma con esempi diversi (con numeri che hanno combinationVal maggiori di 2) dovrei aggiungere di più, quindi non posso escluderlo.

E poi non sono sicuro di cosa succeda se cambio il targetVal diciamo a 60 ed aggiungo il numero 20 al set di coins... 10*2 e 2*10 ad esempio danno 20, significa che il 20 adesso "ruba" il combinationVal del 10 (e lo aumenta di 2) o è più complicato di così? Probabilmente lo è.
Insomma mi sa che devo fare altre prove su carta se voglio davvero risolverlo (al momento non sono più tanto sicuro :D), perchè sono ancora lontanissimo dalla comprensione del problema che mi serve per scrivere un algoritmo decente in C++ :/

 

[BAT]

Per risolvere questo tipo di problemi ti suggerisco, se già non l'hai fatto, di studiare prima in generale la materia che nelle facoltà universitarie si chiama "Algoritmi e strutture dati" (o nomi simili) in varie salse (anche "Ricerca operativa" è utile), nel senso che ci sono corsi di livello "crescente". Affrontare un problema "a forza bruta" non è (quasi) mai semplice e, quando non c'è altro modo, ci sono tecniche che permettono di farlo in modo efficiente "tagliando" di netto passi di calcolo che non portano a una buona soluzione (greedy, backtracking, branch and bound). Studierai una serie di algoritmi di ottimizzazione su problemi noti, da cui potrai trarre spunto per risolvere i problemi che affronti. Non ti nascondo che è un percorso lungo (e spesso difficoltoso) ma vedo che sei MOLTO appassionato, se lo intraprenderai per te oltre che istruttivo sarà pure divertente.

 

[Marcus Aseth]

Per risolvere questo tipo di problemi ti suggerisco, se già non l'hai fatto, di studiare prima in generale la materia che nelle facoltà universitarie si chiama "Algoritmi e strutture dati" (o nomi simili) in varie salse (anche "Ricerca operativa" è utile), nel senso che ci sono corsi di livello "crescente". Affrontare un problema "a forza bruta" non è (quasi) mai semplice e, quando non c'è altro modo, ci sono tecniche che permettono di farlo in modo efficiente "tagliando" di netto passi di calcolo che non portano a una buona soluzione (greedy, backtracking, branch and bound). Studierai una serie di algoritmi di ottimizzazione su problemi noti, da cui potrai trarre spunto per risolvere i problemi che affronti. Non ti nascono che è un percorso lungo (e spesso difficoltoso) ma vedo che sei MOLTO appassionato, se lo intraprenderai per te oltre che istruttivo sarà pure divertente.

Mi pare una buona idea, visto che mi rendo conto di star cercando di re-inventare la ruota per problemi che son gia stati risolti... :D
Ed avendo seguito un percorso da autodidatta, mi rendo anche conto di non aver mai letto nulla al riguardo (se non quello che è incluso in libri che però puntavano principalmente ad insegnare il C++)
Appena ho la possibilità di procurarmene uno e dedicargli la giusta attenzione, ci provo (dico questo perchè al momento quello che ha maggiore priorità nella mia lista di libri da comprare è "A Dictionary of Intermediate Japanese Grammar" :D)

 

[Andretti60]

Per risolvere questo tipo di problemi ti suggerisco, se già non l'hai fatto, di studiare prima in generale la materia che nelle facoltà universitarie si chiama "Algoritmi e strutture dati" (o nomi simili) in varie salse (anche "Ricerca operativa" è utile), nel senso che ci sono corsi di livello "crescente". Affrontare un problema "a forza bruta" non è (quasi) mai semplice e, quando non c'è altro modo, ci sono tecniche che permettono di farlo in modo efficiente "tagliando" di netto passi di calcolo che non portano a una buona soluzione (greedy, backtracking, branch and bound). Studierai una serie di algoritmi di ottimizzazione su problemi noti, da cui potrai trarre spunto per risolvere i problemi che affronti. Non ti nascondo che è un percorso lungo (e spesso difficoltoso) ma vedo che sei MOLTO appassionato, se lo intraprenderai per te oltre che istruttivo sarà pure divertente.

Concordo in pieno. In informatica si da' grande peso allo studio della teoria degli alberi (teoria dei grafi), in quanto permette di risolvere un numero enorme di problemi evitando appunto di usare la "forza bruta". Lungi da me tentare di spiegarla in due parole :) vedi link sotto. Basti dire che e' una branca della informatica con basi teoriche molto salde e un buon numero di teoremi e assiomi, ed e' continuamente in evoluzione. E' essenziale nel campo della intelligenza artificiale perché permette di velocizzare gli algoritmi.
Cio' non toglie comunque che questi esercizi di programmazione facciano male, anzi, insegnano proprio a vedere e capire le difficoltà di questi problemi.
https://en.wikipedia.org/wiki/Graph_theory