c - 从动态规划函数中获取值

Question

我正在构造一个递归自下而上动态编程函数，它返回输入零钱的硬币数量。但是，我想修改代码，使该函数还返回一个数组，其中包含为示例返回的硬币值:

Change:9c; #coins:3; 1c: 0, 2c:2, 5c:1

我尝试打印 values[j] 但从硬币元组中只提取了一个硬币。例如:

在迭代 7 中，可能的元组是 (5,1,1),(5,2) 但我只得到每个元组的最后一个元素，即 1， 2 而我想要最后一个元组。

下面是这道题的C代码:

    /**
  * @desc returns the number of coins needed for a particular amount of change
  *       using bottom-up recursive dynamic programming approach.
  * @param int amt  - amount of change to convert to coins.
  *        int values[]  - array of coins available (predefined).
  *        int n  - length of values[].
  *        int a  - current iteration of change (predefined at 1).
  *        int coins[]  - array holding the amount of coins from 1 till amt.
  * @return return coins[amt] - returns the amount of coins.
*/
int ComputeChange(int amt,int values[],int n,int a,int coins [])
{
    printf("\n\na: %d",a);
    printf("\n");
    coins[a]=INT_MAX;
    int j;
    //loops all values of coins
    for (j=0; j<n; j++)
    {

        // if current coin value is smaller or equal than a (the current change value)
        // and if the number of coins at the current amount-the currently looped value of a coin
        // is less than the number of coins at the current amount.
        if ((values[j] <=a)&& (1+coins[a-values[j]]<coins[a]))
        {
            printf("%d,",values[j]);
            coins[a]=1+coins[a-values[j]];
        }
    }
    if (a==amt)
    {
        printf("\n");
        return coins[amt];
    }
    else
    {
        return ComputeChange(amt,values,n,a+1,coins);
    }
}

int main()
{
    int i;
    int counter=0;
    int answer;
    int choice=0;
    int array[] = {1,2,5,10,20,50,100,200};
    int answers[100][2];
    int n= sizeof(array)/sizeof(array[0]);
    while (1)
    {
        printf("Enter change to turn into coins, -1 to exit:\n");
        scanf("%d",&choice);
        if (choice==-1)
        {
            exit(0);
        }
        int isFound=0;
        int coins[choice];  //array of number of coins needed up to amt
        coins[0]=0;
        for (i=0; i<counter; i++)
        {
            if (choice==answers[i][0])
            {
                printf("Cached Value: ");
                answer=answers[i][1];
                isFound=1;
            }

        }
        if (!isFound)
        {
            answer=ComputeChange(choice,array,n,1,coins);
        }
        answers[counter][0]=choice;
        answers[counter++][1]=answer;
        printf("Number of coins: %d\n\n",answer);

    }


    return 0;
}

Answer 1

您没有现成的信息。

如果您为每次迭代存储最后一个硬币，您可以打印这些硬币:

/**
  * @desc returns the number of coins needed for a particular amount of change
  *       using bottom-up recursive dynamic programming approach.
  * @param int amt  - amount of change to convert to coins.
  *        int values[]  - array of coins available (predefined).
  *        int n  - length of values[].
  *        int a  - current iteration of change (predefined at 1).
  *        int coins[]  - array holding the amount of coins from 1 till amt.
  * @return return coins[amt] - returns the amount of coins.
*/
int ComputeChange(int amt,int values[],int n,int a,int coins [], int lastcoin [])
{
    printf("\n\na: %d",a);
    printf("\n");
    coins[a]=INT_MAX;
    int j;
    int tmp;
    //loops all values of coins
    for (j=0; j<n; j++)
    {

        // if current coin value is smaller or equal than a (the current change value)
        // and if the number of coins at the current amount-the currently looped value of a coin
        // is less than the number of coins at the current amount.
        if ((values[j] <=a)&& (1+coins[a-values[j]]<coins[a]))
        {
            lastcoin[a] = values[j];
            coins[a]=1+coins[a-values[j]];
        }
    }
    if (a==amt)
    {
        j = amt;
        while (j>0) {
            printf("%d, ", lastcoin[j]);  // Print the coins that make up the amount 
            j -= lastcoin[j];
        }
        printf("\n");
        return coins[amt];
    }
    else
    {
        return ComputeChange(amt,values,n,a+1,coins);
    }
}