Intr-un restaurant un meniu este format din 3 feluri de mancare. Exista patru preparate culinare pt felul 1 , cinci preparate culinare pt felul 2 si trei preparare culinare pt felul 3. Fiecare preparat culinar are un pret si un numar de calorii. Sa se genereze toate meniurile pe care le poate comanda o persoana , care sa nu depășească suma s si numarul de calorii c. Datele de citesc dintr-un fisier text , astfel : de pe primul rand, suma s si numarul de calorii, de le randul urmator , in ordine, pretul fiecarui preparat culinar ,si , de pe ultimul rand , in aceeasi ordine , caloriile fiecarui preparat culinar.
Se rezolva cu metoda backtraking , puteti sa lasati si codul(c++)?
Răspunsuri la întrebare
Răspuns:
#include <iostream>
#include <fstream>
using namespace std;
const int MAX_N = 12; // numarul maxim de preparate culinare
int s, c; // suma si numarul de calorii
int price[MAX_N], calories[MAX_N]; // preturile si caloriile preparatelor
int chosen[MAX_N]; // preparatele alese
void readData() {
ifstream fin("data.txt");
fin >> s >> c;
for (int i = 0; i < MAX_N; i++) fin >> price[i];
for (int i = 0; i < MAX_N; i++) fin >> calories[i];
fin.close();
}
bool isSolution(int k, int cost, int cal) {
return (k == MAX_N) && (cost <= s) && (cal <= c);
}
void printSolution() {
for (int i = 0; i < MAX_N; i++)
cout << chosen[i] << " ";
cout << endl;
}
void backtrack(int k, int cost, int cal) {
if (isSolution(k, cost, cal)) printSolution();
else {
for (int i = 0; i < 4; i++) { // pentru felul 1
chosen[k] = i;
backtrack(k + 1, cost + price[i], cal + calories[i]);
}
for (int i = 4; i < 9; i++) { // pentru felul 2
chosen[k] = i;
backtrack(k + 1, cost + price[i], cal + calories[i]);
}
for (int i = 9; i < 12; i++) { // pentru felul 3
chosen[k] = i;
backtrack(k + 1, cost + price[i], cal + calories[i]);
}
}
}
int main() {
readData();
backtrack(0, 0, 0);
return 0;
}