I solve the problem of the exchange of coins. The condition is shown below. The problem is that all the solutions that I have experienced occupy a lot of memory. And not applicable for large input data such as for 1 000 000 000 . The question is how can you optimize solutions for large numbers? Or maybe there is some more effective idea to solve this problem?

The task:

1≤n≤30 numbers 1≤n≤30 and 1≤w≤10^9 and the set of numbers 1≤v[1],…,v[n]≤10^9 find the minimum number k for which the number w can be represented as the sum of k numbers from the set {v[1],…,v[n]} . Each number in the set can be used any number of times. It is known that there is a unit in the set and that for any pair of numbers from the set one of them is divided by the other. It is guaranteed that in the optimal answer the number of items does not exceed 10^4 .

Print the number k and the terms themselves.

 Sample Input: 4 90 1 2 10 50 Sample Output: 5 50 10 10 10 10

C ++ solution:

 #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 solution. Option 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 solution. Option 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),

    4 answers 4

    Intermediate arrays are not needed:

     int min_coins(std::vector<int> coins, int target, std::vector<int> & result) { int count = 0; result.clear(); std::sort(coins.begin(), coins.end()); // отсортируем по возростанию for( auto coin = coins.rbegin() // перебираем от наибольших ; coin != coins.rend() // до наименьших && target > 0 // если поделили нацело выходим ; ++coin ) { if(target >= (*coin)) { count += target / (*coin); target = target % (*coin); // остаток от деления на coin result.push_back(*coin); } } return count; }

    Due to the fact that we always divide the target into the largest possible, result always incremented by the smallest possible number. At the end we have 1 by condition.

    We include those that are smaller than the target target amount in the list of selected coins - once the coin is smaller, it can be exchanged.

    Why does the algorithm produce the best solution? Because the condition says:

    for any pair of numbers from the set one of them is divided by another

    This means that any number in the set is divided by any number in the set less than the first. In fact, the number before 1 should be the GCD of all numbers. Therefore, we have the right to sort them out and act as I propose. If they did not have a NOD, then yes, it would be necessary to sort out exchange options.

    • And how to get the coins themselves? Brute force Those. the algorithm gave out, for example, the number 5. Does the algorithm produce the optimal solution? How to continue to get these same 5 coins? - abg
    • @abg updated the answer - Cerbo
    • @abg algorithm gives out not optimal, but the best solution - Cerbo

    Python solution

     def solution(): target = 200 coins = (1, 2, 5, 10, 20, 50, 100, 200) ways = [1] + [0]*target for coin in coins: for i in range(coin, target+1): ways[i] += ways[i-coin] return ways[target] if __name__ == '__main__': print(solution())
    • The condition says, “for any pair of numbers from the set, one of them is divisible by the other,” and you do not divide 5 by 2 - Cerbo
    • I showed a general solution of the problem with minimal memory usage. For your purposes, changing the input is not a problem. - ddipp
    • one
      Your algorithm counts the number of exchange methods. And according to the problem, you need to find the optimal solution, i.e. The minimum number of coins that can be used to exchange the input amount. In general, I did not understand, we need more detailed explanations. - abg
     def solve_sum(num_array, value): dividers = [i for i in num_array if i <= value] dividers = sorted(dividers, reverse=True) res = [] n = 0 while value: res += [dividers[n]] * (value // dividers[n]) k = (value // dividers[n]) value %= dividers[n] n += k return str(n)+' '+" ".join(map(str, res)) results = input().split(' ') results = [int(i) for i in results] value = results[1] num_array = results[2:] print(solve_sum(num_array, value))

    Actually what's wrong with this decision?

      I would suggest this in the event of a canonical entrance.

       def get_changing(coins: list, count: int) -> list: """ Размен :param coins: упорядоченный массив монет [1, 3, ...] :param count: сумма :return: размен вида [[coin, count], ...] """ if count < 1: return [] # единица всегда есть res = [[1, count]] # количество монет изначально худший вариант - равно сумме cnt = count # идем снизу вверх по номиналам и на каждом шаге либо улучшаем # ситуацию либо не делаем ничего for i in coins[1:]: if count < i: return res # найдем размен для остатка n_res = get_changing(coins, count % i) # посчитаем новое количество монет n_cnt = (count // i) + sum(v[1] for v in n_res) # стало лучше ? if n_cnt < cnt: res, cnt = n_res, n_cnt res.append([i, count // i]) return res