我正在构造一个recursive bottom-up dynamic programming function来返回输入的硬币数量。但是，我想修改代码，使函数也返回一个数组，返回硬币的值，例如：
Change:9c; #coins:3; 1c: 0, 2c:2, 5c:1
我试着打印
values[j]，但只有一枚硬币是从一组硬币中提取出来的。例如：在
iteration 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;
}
最佳答案
你没有现成的信息。
如果每次迭代都存储最后一个硬币，则可以打印硬币：
/**
* @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);
}
}
关于c - 从动态编程功能获取值，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/34330426/