Решаю задачу о размене монет. Условие приведено ниже. Проблема в том, что все решения, которые я испытал занимают много памяти. И не применимы для больших входных данных например, для 1 000 000 000
. Вопрос в том как можно оптимизировать решения для больших чисел? Или может есть какая-нибудь более эффективная идея для решения этой задачи?
Условие задачи:
По данным числам 1≤n≤30
и 1≤w≤10^9
и набору чисел 1≤v[1],…,v[n]≤10^9
найдите минимальное число k
, для которого число w можно представить как сумму k
чисел из набора {v[1],…,v[n]}
. Каждое число из набора можно использовать сколько угодно раз. Известно, что в наборе есть единица и что для любой пары чисел из набора одно из них делится на другое. Гарантируется, что в оптимальном ответе число слагаемых не превосходит 10^4
.
Выведите число k
и сами слагаемые.
Sample Input:
4 90 1 2 10 50
Sample Output:
5 50 10 10 10 10
Решение на C++:
#include <iostream>
#include <vector>
#include <string>
#include <climits>
#include <algorithm>
std::vector<int> get_best_coins(std::vector<int>& coins, int target) {
std::vector<int> costs;
costs.push_back(0);
std::vector<int> coins_used;
for (int i = 1; i <= target; i++) {
int bestCost = INT_MAX;
int bestCoin = -1;
for (std::vector<int>::iterator coin = coins.begin() ; coin != coins.end(); ++coin){
if (*coin <= i) {
int cost = 1 + costs[i - *coin];
if (cost < bestCost) {
bestCost = cost;
bestCoin = *coin;
}
}
}
costs.push_back(bestCost);
coins_used.push_back(bestCoin);
}
std::vector<int> ret;
while (target > 0) {
ret.push_back(coins_used[target -1]);
target -= coins_used[target - 1];
}
return ret;
}
int main() {
int n;
std::cin >> n;
int w;
std::cin >> w;
std::vector<int> v;
int input;
for (int i = 0; i < n; i++) {
std::cin >> input;
v.push_back(input);
}
std::sort(v.begin(), v.end());
std::vector<int> result = get_best_coins(v, w);
std::cout << result.size() << " ";
for (std::vector<int>::iterator coin = result.begin() ; coin != result.end(); ++coin) {
std::cout << *coin << " ";
}
return 0;
}
Решение на Python. Вариант 1:
import sys, math
def dpMakeChange(coinValueList,change,minCoins,coinsUsed):
for cents in range(change+1):
coinCount = cents
newCoin = 1
for j in [c for c in coinValueList if c <= cents]:
if minCoins[cents-j] + 1 < coinCount:
coinCount = minCoins[cents-j]+1
newCoin = j
minCoins[cents] = coinCount
coinsUsed[cents] = newCoin
return minCoins[change]
def printCoins(coinsUsed,change):
coin = change
while coin > 0:
thisCoin = coinsUsed[coin]
print(thisCoin),
coin = coin - thisCoin
def main():
input = sys.stdin.read()
tokens = input.split()
n = int(tokens[0])
amnt = int(tokens[1])
clist = []
for i in range(n):
clist.append(int(tokens[i + 2]))
coinsUsed = [0]*(amnt+1)
coinCount = [0]*(amnt+1)
print("{0}".format(dpMakeChange(clist,amnt,coinCount,coinsUsed))),
printCoins(coinsUsed,amnt)
main()
Решение на Python. Вариант 2:
import sys
def get_best_coins(coins, target):
costs = [0]
coins_used = [None]
for i in range(1,target + 1):
bestCost = sys.maxsize
bestCoin = -1
for coin in coins:
if coin <= i:
cost = 1 + costs[i - coin]
if cost < bestCost:
bestCost = cost
bestCoin = coin
costs.append(bestCost)
coins_used.append(bestCoin)
ret = []
while target > 0:
ret.append(coins_used[target])
target -= coins_used[target]
return ret
input = sys.stdin.read()
tokens = input.split()
n = int(tokens[0])
target = int(tokens[1])
coins = []
for i in range(n):
coins.append(int(tokens[i + 2]))
result = get_best_coins(coins, target)
print (len(result)),
for p in result:
print(p),