Aiuto coin change

Ciao, ho un problema con l’esercizio coinchange: un singolo output non è corretto nel subtask 3. Non riesco proprio a capire dove sia il problema, ho provato a cambiare i tipi delle variabili ma nulla. Allego il codice:

#include <fstream>
#include <iostream>
#include <cmath>

using namespace std;

// vettore preso in input con numero di monete e banconote per ogni valore
long long V[15];

// vettore di moltiplicatori che verrà usato per trasformare le "quantità" nel loro effettivo valore
long double x[15] = {0.01, 0.02, 0.05, 0.1, 0.2, 0.5, 1, 2, 5, 10, 20, 50, 100, 200, 500};

//vettore restituito in output con gli scambi effettuati
long long sol[15] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

int main()
{

    //stream da file
    //commentare il prossimo rigo permetterà l'inserimento da console
    ifstream cin("input.txt");
    ofstream cout("output.txt");

    //lettura delle 15 quantita' di banconote o monete dallo stream di input
    for (int i = 0; i < 15; i++)
    {
        cin >> V[i];
    }

    //variabile per sommare il valore totale effettivo in euro del vettore di banconote e monete.
    long double somma = 0;

    //somma
    for (int i = 0; i < 15; i++)
    {
        //ogni quantità viene moltiplicata per il rispettivo moltiplicatore (es. 35*0.02 è la moltiplicazione che avviene con 35 monete da 2 centesimi)
        somma += V[i] * x[i];
    }

    //variabile
    long double tmp = 0;
    for (int i = 14; i > -1; i--)
    {
        //ogni volta si cerca di ottenere il numero più alto di monete o banconote (es. se ho 1516€ questa operazione restituisce al primo ciclo 3.032)
        tmp = somma / x[i];
        //nel vettore delle soluzioni si andrà a porre il valore ottenuto in tmp, di cui prendiamo solo la parte intera
        sol[i] = static_cast<long long> (floor(tmp));
        somma -= x[i] * sol[i];
    }

    for (int i = 0; i < 15; i++)
        cout << sol[i] << " ";
    cout << endl;
    return 0;
}

Ciao, prova a sostituire

static_cast<long long> (floor(tmp));

con

static_cast<long long> (tmp + 0.0001);
1 Mi Piace

In generale quando puoi evitare di usare i floating point ti consiglierei di non usarli (qui basterebbe avere i valori moltiplicati per 100)

1 Mi Piace

Funziona, ma non capisco perché. Immagino riguardi in qualche modo la conversione fra tipi?

Lavorando con i numeri in virgola mobile possono verificarsi degli errori di precisione, in questo caso la variabile tmp conteneva un valore del tipo 41.999999999997. Convertendolo veniva arrotondato all’intero inferiore ovvero 41 quando invece il valore corretto era 42. Sommando alla variabile un numero molto piccolo, ad esempio 0.0001 oppure 1e-6, puoi prevenire questo comportamento scorretto.

Come suggerito da @MyK_00L, cerca di evitare di usare i numeri in virgola mobile il più possibile, ma se proprio non puoi farne a meno, non trascurare gli errori di precisione!

1 Mi Piace

Perfetto adesso è chiaro, grazie mille