1

Решаю задачу о размене монет. Условие приведено ниже. Проблема в том, что все решения, которые я испытал занимают много памяти. И не применимы для больших входных данных например, для 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),
0

4 ответа 4

1

Промежуточные массивы не нужны:

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;
}

Из-за того, что мы target всегда делим на наибольшее из возможных, result всегда наращивается на наименьшее из возможных чисел. В конце у нас 1 по условию.

В список выбранных монет включаем те, которые меньше целевой суммы target - раз монета меньше значит ей можно разменять.

Почему алгоритм выдает наилучшее решение? Потому, что в условии сказано:

для любой пары чисел из набора одно из них делится на другое

Это означает, что любое число из набора делится на любое число из набора меньшее первого. По сути, число перед 1 должно быть НОД всех чисел. Поэтому мы имеем право их отсортировать и действовать как я предлагаю. Если бы они не имели НОД, то тогда да, нужно было бы перебирать варианты размена.

3
  • А как получить сами монеты? Перебором? Т.е. алгоритм выдал например число 5. Алгоритм выдает оптимальное решение? Как дальше получить эти самые 5 монет?
    – abg
    7 дек 2015 в 10:50
  • @abg обновил ответ
    – Cerbo
    7 дек 2015 в 10:52
  • @abg алгоритм выдает не оптимальное, а лучшее решение
    – Cerbo
    7 дек 2015 в 11:04
1

Решение на Питоне

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())
3
  • В условии сказано "для любой пары чисел из набора одно из них делится на другое", а у вас 5 на 2 не делится
    – Cerbo
    7 дек 2015 в 9:25
  • Я показал общее решение задачи с минимальным использованием памяти. Для своих целей изменить входные данные - не проблема.
    – ddipp
    7 дек 2015 в 10:38
  • 1
    Ваш алгоритм считает количество способов размена. А по задаче нужно найти оптимальное решение, т.е. минимальное количество монет, которым можно разменять входную сумму. В общем я не понял, нужны более детальные пояснения.
    – abg
    7 дек 2015 в 10:45
0
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))

Собственно что в таком решении не правильно?

0

Я бы вот что предложил на случай канонического входа.

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

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.