Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- Sao varios brutes, um para cada tarefa do problema.
- O codigo roda em uns 21 segundos (na minha maquina) e tem a seguinte saida:
- nova moeda: 18, soma: 319
- ---------//--------------
- novas moedas: 8 37, soma: 281
- -----------//--------------
- novo conjunto: 1 5 16 23 33 soma: 333
- */
- #include <bits/stdc++.h>
- using namespace std;
- #define int long long
- //Funcao para calcular, dado um conjunto de moedas, qual a soma das quantidades de moedas necessarias para formar cada valor
- //Eh um knapsack O(#moedas * #valores)
- int calcSum(const vector<int> &moedas)
- {
- vector<int> dp(101, (int)1e9); dp[0] = 0;
- for (int x = 1; x <= 100; x++)
- for (auto moeda : moedas)
- if (moeda <= x)
- dp[x] = min(dp[x], dp[x-moeda]+1);
- return accumulate(dp.begin(), dp.end(), 0LL);
- }
- void bt(int id, vector<int> &conj, vector<int> &atual, int m, int &resp)
- {
- if (id == 5)
- {
- int soma = calcSum(atual);
- if (soma < resp) resp = soma, conj = atual;
- return;
- }
- if (m > 100) return;
- for (int x = m; x <= 100; x++)
- {
- atual.push_back(x);
- bt(id+1, conj, atual, x+1, resp);
- atual.pop_back();
- }
- }
- int32_t main()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- vector<int> moedas = {1, 5, 10, 25, 50, 100};
- int resp = (int)1e9;
- int nova = 0;
- //Acha a moeda que, junto as outras, miniza a soma total
- //So um brute. O(#valores * knapsack)
- for (int i = 1; i <= 100; i++)
- {
- moedas.push_back(i);
- int soma = calcSum(moedas);
- if (soma < resp) nova = i, resp = soma;
- moedas.pop_back();
- }
- cout << "nova moeda: " << nova << ", soma: " << resp << '\n';
- cout << "---------//--------------" << '\n';
- //Acha o par de moedas que miniza a soma total
- //Mesma coisa que o problema de uma moeda, mas com duas. O(#valores^2 * knapsack)
- resp = (int)1e9; pair<int, int> novas = {0,0};
- for (int i = 1; i <= 100; i++)
- {
- moedas.push_back(i);
- for (int j = i+1; j <= 100; j++)
- {
- moedas.push_back(j);
- int soma = calcSum(moedas);
- if (soma < resp) novas = make_pair(i, j), resp = soma;
- moedas.pop_back();
- }
- moedas.pop_back();
- }
- cout << "novas moedas: " << novas.first << " " << novas.second << ", soma: " << resp << '\n';
- cout << "-----------//--------------" << '\n';
- vector<int> conj = {1}, atual = {1}; resp = (int)1e9;
- //Acha o conjunto de 5 moedas que tem menor soma. Precisa ter 1, ent sempre esta no grupo
- //Uma backtrack. O(escolhe(99, 4) * knapsack)
- bt(1, conj, atual, 2, resp);
- cout << "novo conjunto: "; for (auto x : conj) cout << x << " "; cout << "soma: " << resp << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
