applidiumResto_corrigé, C++ (clang)

applidiumResto_corrigé

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <limits>
#include <array>

using namespace std;

static const array<string, 7> daysOfTheWeek = {{"Lundi", "Mardi", "Mercredi", "Jeudi", "Vendredi", "Samedi", "Dimanche"}};

struct Meal {
	string name;
	int cal;
        
	Meal(string n, int c) : name(n), cal(c)
	{}
    
    ~Meal() = default;
};

void display(ostream & str, const vector<Meal> & vect)
{
    for (int i = 0; i < daysOfTheWeek.size(); ++i) {
        str << daysOfTheWeek[i] << " : " << vect[i].name << endl;   
    }
}

// return the sum of the calories and the vector computed from checking the k (here 7) combinations of n items (size of vect input)
// input vector has to be at least of size k
pair<int, string> computeResult(const vector<Meal> &vectResto, int targetCal)
{
    string bitmask(daysOfTheWeek.size(), 1); // 7 leading 1 = > 1111 111  (1 is an ASCII code here, not corresponding to '1')
    bitmask.resize(vectResto.size(), 0); // n-k trailing 0 => 1111 1110 00..00 (0 in ASCII => empty space)
    string bitmaskSaved = bitmask;
    // set the closest calories to target to the maximum
    int closestToTarget = numeric_limits<int>::max();
    // build vector and permute bitmask
    do {
        int sum = 0;
        for (int i = 0; i < vectResto.size(); ++i) {
            sum += bitmask[i] * vectResto[i].cal;
        }
        if (sum == targetCal) {
            // perfect solution found
            return make_pair(sum, bitmask);
        } else if (abs(sum - targetCal) < abs(closestToTarget - targetCal)) {
            closestToTarget = sum;
            bitmaskSaved = bitmask;
        }
    } while (prev_permutation(bitmask.begin(), bitmask.end()));  // previous permutation in lexically order
    return make_pair(closestToTarget, bitmaskSaved);
}

int main()
{
	int nbCal;
	cin >> nbCal; cin.ignore();
	string str;
	vector<Meal> vectResto;
	while (getline(cin, str)) {
		size_t posEgal = str.find("=");
		if (posEgal == string::npos) {
			cout << "error, the input is missing the = symbol ! exiting the program";
			return 1;
		}
		string name = str.substr(0, posEgal - 1);
		int cal = stoi(str.substr(posEgal + 2));
		vectResto.push_back(Meal(name, cal));
	}
    if (vectResto.size() < daysOfTheWeek.size()) {
        cout << "ERROR : not enough restaurants to build the planning of the week" << endl;
        return 1;
    }
	// sorting the vector according to the calories (if you want to start the week healthy and finish fat !)
	// sort(vectResto.begin(), vectResto.end(), [](const Meal & m1, const Meal & m2) {return (m1.cal == m2.cal) ? (m1.name < m2.name) : (m1.cal < m2.cal); });
    
    pair<int, string> result;
    vector<Meal> planning;
    result = computeResult(vectResto, nbCal);
    for (int i = 0; i < vectResto.size(); ++i) {
        if (result.second[i]) {
            planning.push_back(vectResto[i]);
        }
    }
    display(cout, planning);
    cout << "Total : " << result.first << " kcal, contre " << nbCal << " kcal demandées" << endl;
    return 0;
}


run \| edit \| history \| help	0