Изменение задачи «Смена монеты» для отслеживания того, какая монета используется (не минимальное количество)

Question

Я написал простой алгоритм смены монет, который в настоящее время находит минимальное количество монет, необходимое для соответствия сумме, необходимой для покупки чего-либо.Я пытаюсь изменить его так, чтобы он отслеживал минимальное количество монет каждого номинала, которое будет использоваться, и я немного отстала.Таким образом, если вы передадите число 6 в функцию, то это скажет, что минимальное количество монет, которое нужно - 2 (у меня это уже есть), и что комбинация монет для этого - монета 4 цента и 2центовая монетаВот мой код:

coins[5] = {1, 2, 4, 17, 28} //effectively kills any use of greedy algortihms
count[m];
int coins_needed_for(int m) {


//Initilization- fills array w/ -1s
for (int z = 1; z < m+1; z++) {
    count[z] = -1;      
}//for  

//fills in appropriate values
for (int j = 0; j < 5; j++) {   
    if (coins[j] < m)
        count[coins[j]] = 1;    
    else if (coins[j] == 1)
        return 1;   
    else
        break;
}//for  


//Execution 
for (int p = 1; p < m+1; p++) {     
    if (count[p] == -1) {           
        int min = 10000 //poor subsitute for infinity;

        for (int i = 0; i < 5; i++) {               

            if (coins[i] <= p) {                            
                if (count[p-coins[i]] + 1 < min) {
                    min = count[p-coins[i]] + 1;                            
                }                   
            }//if           
        count[p] = min;         
        }//for          
    }//if               
}//for  
return count[m];
}

Я понимаю, что требуется, я просто не уверен, что лучший способ это сделать.Должен ли я создать другой массив, и если да, то должен ли он быть двухмерным?Могу ли я создать структуру, которая хранит счет каждой монеты, используемой для каждого возможного m?Я открыт для любых предложений.Я не обязательно ищу определенный ответ, просто указатели и полезные советы.Запрашивать ответ на поставленную задачу просто неправильно.Спасибо!

Answer 1

Это очень старая проблема, известная как «проблема изменения».Посмотрите, что Википедия говорит об этом.

Это форма проблемы с рюкзаком, которая не является тривиальной проблемой.

Answer 2

Вы можете использовать деление и модуль, чтобы сделать это проще. Я приведу пример.

afterQuarterTotal = totalAmount % 25; 
numberOfQuarters = (totalAmount - afterQuarterTotal) / 25; 
afterDimeTotal = aftgerQuarterTotal % 10; 
numberOfDimes = (afterQuarterTotal - afterDimeTotal) / 10;

и так далее ...

Answer 3

/ * Проблема с обменом монет

Входные данные: Первая линия ожидает сумму Вторая строка ожидает количество монет Третья строка содержит монеты в порядке возрастания номиналов Предполагается бесконечная подача монет

Ouput Технические характеристики: Каждый случай отображается сначала с монетой самого низкого достоинства, а затем со следующим самым большим достоинством. Случаи разделены линиями Если сумма не может быть найдена, -1 печатается

* /

#include<iostream>
using namespace std;
int *num,*coins,*maxC,n,amount,flag=0,stop=0;
int sum()
{
    int i=0,j;
    int sum=0;
    for(i=0;i<n;++i)
        for(j=0;j<num[i];++j)
            sum+=coins[i];
    return sum;
}
void print()
{
    int i,j;
    for(i=0;i<n;++i)
    {
        for(j=0;j<num[i];++j)
            cout<<coins[i]<<" ";
    }
    cout<<endl;
}
void printNum()
{
    int i;
    for(i=0;i<n;++i)
        cout<<num[i]<<" ";
    cout<<endl;
}
void nextIter()
{
    int i,j;
    int stat=0;
    //printNum();   //Remove the comment if you want to see the values of num array in every iteration
    for(i=0;i<n;++i)
    {
        if(num[i]==0)
            stat=1;
        else
        {
            stat=0;
            break;
        }
    }
    if(stat)
    {
        stop=1;
        return ;
    }
    for(i=n-1;i>=0;--i)
    {
        int dec=0;
        if(num[i]==0)
        {
            dec=1;
            num[i]=maxC[i];
        }
        else
        {
            --num[i];
            return ;
        }
    }
}
int find()
{
    while(!stop)
    {
        if(amount==sum())
        {
            flag=1;
            print();
        }
        nextIter();
    }
}
int main()
{
    int i;
    cout<<"\nEnter amount:";
    cin>>amount;
    cout<<"\nEnter number of coins:";
    cin>>n;
    coins=new int[n];
    maxC=new int[n];//contains maximum number of each denomination required
    num=new int[n];//contains current number of each denomination required
    for(i=0;i<n;++i)
    {
        cin>>coins[i];
        num[i]=maxC[i]=amount/coins[i];
    }
    find();
    if(!flag)
        cout<<"-1";
    cout<<endl;
    system("pause");
    return 0;
}

Answer 4

void recursive_program(int coins) 

{
    int times;
    if (coins==0)                                                
           return;

if (coins>=28)                                                  
    {                                                             
    times=coins/28;
    cout<<times; 
    cout<<" * 28 for\t\t"<<times*28<<endl;
    return recursive_program(coins%28);
}

if (coins>=17)                                                
{
    times=coins/17;
    cout<<times; 
    cout<<" * 17 for\t\t\t "<<times*17<<endl;
    return recursive_program(coins%17);
}

if (coins>=4)                                                 
{
    times=coins/4;
    cout<<times;
    cout<<" * 4 for\t\t\t "<<times*4<<endl;
    return recursive_program(coins%4);
}
if (coins>=2)                                                 
{
    times=coins/2;
    cout<<times;
    cout<<" * 2 for\t  "<<times*2<<endl;
    return recursive_program(coins%2);
}

if (coins>=1)                                                 
{
    times=coins/1;
    cout<<times;
    cout<<" * 1 for\t\t\t\t  "<<times<<endl;
    coins=0;
    return recursive_program(coins);
}
}