applidiumResto_NicolasCarre, C++ (clang)

applidiumResto_NicolasCarre

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

using namespace std;

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

ostream& operator<<(ostream &str, const vector<Meal> & vect)
{
    string week[] = { "Lundi", "Mardi", "Mercredi", "Jeudi", "Vendredi", "Samedi", "Dimanche" };
    for (int i = 0; i < 7; ++i) {
     str << week[i] << " : " << vect[i].name << endl;   
    }
	return str;
}

// 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, vector<Meal>> computeResult(const vector<Meal> &vectResto, int k, int targetCal)
{
    string bitmask(k, 1); // k 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)
    vector<Meal> vect7Resto;
    vector<Meal> curVect;
    // 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) {
            if (bitmask[i]) {
                sum += vectResto[i].cal;
                curVect.push_back(vectResto[i]);
            }          
        }
        if (sum == targetCal) {
            // perfect solution found
            return make_pair(sum, curVect);
        } else if (abs(sum-targetCal) < abs(closestToTarget - targetCal)) {
            closestToTarget = sum;
            vect7Resto = curVect;
        }
        curVect.clear();
    } while (prev_permutation(bitmask.begin(), bitmask.end()));  // previous permutation in lexically order
    return make_pair(closestToTarget, vect7Resto);
}

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() < 7) {
        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, vector<Meal>> result;
    result = computeResult(vectResto, 7, nbCal);
    cout << result.second;
    cout << "Total : " << result.first << " kcal, contre " << nbCal << " kcal demandées" << endl;
    return 0;
}


run \| edit \| history \| help	0

λ

                                      .NET NoSQL database for rapid development