Algorithms/Backtracking.cpp at main · ldcss/Algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
using namespace std;

class Compra{
    public:
    int tam;
    int minimo_itens;
    int itens;
    int Q;
    int cont;
    int *preco;
    Compra(){
        cont = 0;
        itens = 0;
    };
    void backtracking(int posicao, int somatorio){
        if (tam==posicao){
            return;
        }
        if (somatorio+preco[posicao]<=Q){
            itens++;
            if (itens>=minimo_itens){
                cont++;
            }
            backtracking(posicao+1, somatorio+preco[posicao]);
            itens--;
        }
        backtracking(posicao+1, somatorio);
    }
};

int main(){
    int casos, iterador = 0;
    cin >> casos;
    while (casos){
        Compra compra;
        int pos = 0, somatorio= 0, valor;
        cin >> compra.tam;
        compra.preco = new int[compra.tam];
        for (int i = 0; i < compra.tam; i++){
            cin >> valor;
            compra.preco[i] = valor;
        }
        cin >> compra.minimo_itens >> compra.Q;
        if (compra.minimo_itens==0){
            compra.cont = 1;
        }
        compra.backtracking(pos, somatorio);
        cout << "caso " << iterador << ": " << compra.cont;
        casos--;
        iterador++;
        cout << endl;
    }
}